Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userFaster Approximation for Maximum Independent Set on Unit Disk Graph
70
0
0.0
(
0
)
Added by
Supantha Pandit
Publication date
2016
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
Maximum independent set from a given set $D$ of unit disks intersecting a horizontal line can be solved in $O(n^2)$ time and $O(n^2)$ space. As a corollary, we design a factor 2 approximation algorithm for the maximum independent set problem on unit disk graph which takes both time and space of $O(n^2)$. The best known factor 2 approximation algorithm for this problem runs in $O(n^2 log n)$ time and takes $O(n^2)$ space [Jallu and Das 2016, Das et al. 2016].
rate research
Read More
We improve the running times of $O(1)$-approximation algorithms for the set cover problem in geometric settings, specifically, covering points by disks in the plane, or covering points by halfspaces in three dimensions. In the unweighted case, Agarwal and Pan [SoCG 2014] gave a randomized $O(nlog^4 n)$-time, $O(1)$-approximation algorithm, by using variants of the multiplicative weight update (MWU) method combined with geometric data structures. We simplify the data structure requirement in one of their methods and obtain a deterministic $O(nlog^3 nloglog n)$-time algorithm. With further new ideas, we obtain a still faster randomized $O(nlog n(loglog n)^{O(1)})$-time algorithm. For the weighted problem, we also give a randomized $O(nlog^4nloglog n)$-time, $O(1)$-approximation algorithm, by simple modifications to the MWU method and the quasi-uniform sampling technique.
We give a polynomial-time constant-factor approximation algorithm for maximum independent set for (axis-aligned) rectangles in the plane. Using a polynomial-time algorithm, the best approximation factor previously known is $O(loglog n)$. The results are based on a new form of recursive partitioning in the plane, in which faces that are constant-complexity and orthogonally convex are recursively partitioned into a constant number of such faces.
A graph $G$ with $n$ vertices is called an outerstring graph if it has an intersection representation of a set of $n$ curves inside a disk such that one endpoint of every curve is attached to the boundary of the disk. Given an outerstring graph representation, the Maximum Independent Set (MIS) problem of the underlying graph can be computed in $O(s^3)$ time, where $s$ is the number of segments in the representation (Keil et al., Comput. Geom., 60:19--25, 2017). If the strings are of constant size (e.g., line segments, L-shapes, etc.), then the algorithm takes $O(n^3)$ time. In this paper, we examine the fine-grained complexity of the MIS problem on some well-known outerstring representations. We show that solving the MIS problem on grounded segment and grounded square-L representations is at least as hard as solving MIS on circle graph representations. Note that no $O(n^{2-delta})$-time algorithm, $delta>0$, is known for the MIS problem on circle graphs. For the grounded string representations where the strings are $y$-monotone simple polygonal paths of constant length with segments at integral coordinates, we solve MIS in $O(n^2)$ time and show this to be the best possible under the strong exponential time hypothesis (SETH). For the intersection graph of $n$ L-shapes in the plane, we give a $(4cdot log OPT)$-approximation algorithm for MIS (where $OPT$ denotes the size of an optimal solution), improving the previously best-known $(4cdot log n)$-approximation algorithm of Biedl and Derka (WADS 2017).
In 1960, Asplund and Grunbaum proved that every intersection graph of axis-parallel rectangles in the plane admits an $O(omega^2)$-coloring, where $omega$ is the maximum size of a clique. We present the first asymptotic improvement over this six-decade-old bound, proving that every such graph is $O(omegalogomega)$-colorable and presenting a polynomial-time algorithm that finds such a coloring. This improvement leads to a polynomial-time $O(loglog n)$-approximation algorithm for the maximum weight independent set problem in axis-parallel rectangles, which improves on the previous approximation ratio of $O(frac{log n}{loglog n})$.
In this article, we study a generalized version of the maximum independent set and minimum dominating set problems, namely, the maximum $d$-distance independent set problem and the minimum $d$-distance dominating set problem on unit disk graphs for a positive integer $d>0$. We first show that the maximum $d$-distance independent set problem and the minimum $d$-distance dominating set problem belongs to NP-hard class. Next, we propose a simple polynomial-time constant-factor approximation algorithms and PTAS for both the problems.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
