NC-Approximation Schemes for NP- and PSPACE-Hard Problems for Geometric Graphs
From MaRDI portal
Publication:4386448
DOI10.1006/jagm.1997.0903zbMath0894.68105OpenAlexW2028738060MaRDI QIDQ4386448
Richard E. Stearns, Venkatesh Radhakrishnan, S. S. Ravi, Harry B. III Hunt, Madhav V. Marathe, Daniel J. Rosenkrantz
Publication date: 26 April 1998
Published in: Journal of Algorithms (Search for Journal in Brave)
Full work available at URL: https://semanticscholar.org/paper/3be90f190c0fcd38a58002bb3af481016d15064f
Related Items (76)
On pseudo-disk hypergraphs ⋮ The connected domination number of grids ⋮ Degree-constrained decompositions of graphs: Bounded treewidth and planarity ⋮ A PTAS for the Weighted Unit Disk Cover Problem ⋮ On approximating (connected) 2-edge dominating set by a tree ⋮ Consensus Patterns (Probably) Has no EPTAS ⋮ Linear-Time Approximation Algorithms for Unit Disk Graphs ⋮ Approximability of identifying codes and locating-dominating codes ⋮ Parallel algorithm for minimum partial dominating set in unit disk graph ⋮ On Radiocoloring Hierarchically Specified Planar Graphs: $$\mathcal{PSPACE}$$ -completeness and Approximations ⋮ A parallel hybrid greedy branch and bound scheme for the maximum distance-2 matching problem ⋮ POINT SET LABELING WITH SPECIFIED POSITIONS ⋮ Maximum Independent Set on $$B_1$$ B 1 -VPG Graphs ⋮ Randomized on-line algorithms and lower bounds for computing large independent sets in disk graphs ⋮ A linear-time algorithm for minimum \(k\)-hop dominating set of a cactus graph ⋮ Impact of locality on location aware unit disk graphs ⋮ A polynomial-time approximation to a minimum dominating set in a graph ⋮ Efficient independent set approximation in unit disk graphs ⋮ MAX-CUT and MAX-BISECTION are NP-hard on unit disk graphs ⋮ On approximating string selection problems with outliers ⋮ Polynomial time approximation schemes for minimum disk cover problems ⋮ Parallel algorithms for minimum general partial dominating set and maximum budgeted dominating set in unit disk graph ⋮ Optimization problems in dotted interval graphs ⋮ PTAS for Sparse General-valued CSPs ⋮ Distributed connected dominating sets in unit square and disk graphs ⋮ Approximation Algorithms for Geometric Intersection Graphs ⋮ A polynomial-time approximation scheme for the geometric unique coverage problem on unit squares ⋮ Theory and application of width bounded geometric separators ⋮ Shifting Coresets: Obtaining Linear-Time Approximations for Unit Disk Graphs and Other Geometric Intersection Graphs ⋮ On the Power of Lookahead in Greedy Scheme for Finding a Minimum CDS for Unit Disk Graphs ⋮ Algorithms for the minimum weight \(k\)-fold (connected) dominating set problem ⋮ Analysing local algorithms in location-aware quasi-unit-disk graphs ⋮ Approximation algorithms for finding and partitioning unit-disk graphs into co-\(k\)-plexes ⋮ Shifting strategy for geometric graphs without geometry ⋮ Efficient sub-5 approximations for minimum dominating sets in unit disk graphs ⋮ Approximation algorithms for intersection graphs ⋮ DISTRIBUTED SPANNERS WITH BOUNDED DEGREE FOR WIRELESS AD HOC NETWORKS ⋮ Dispersing and grouping points on planar segments ⋮ ROMAN DOMINATION AND ITS VARIANTS IN UNIT DISK GRAPHS ⋮ On the complexity of bandwidth allocation in radio networks ⋮ Improper colouring of (random) unit disk graphs ⋮ Packing triangles in low degree graphs and indifference graphs ⋮ Minimum vertex cover in ball graphs through local search ⋮ Polynomial-time approximation schemes for piercing and covering with applications in wireless networks ⋮ The within-strip discrete unit disk cover problem ⋮ Structure of polynomial-time approximation ⋮ On connected domination in unit ball graphs ⋮ On Approximating (Connected) 2-Edge Dominating Set by a Tree ⋮ Independent set of intersection graphs of convex objects in 2D ⋮ Minimum vertex cover in rectangle graphs ⋮ Approximating minimum independent dominating sets in wireless networks ⋮ Decision and approximation complexity for identifying codes and locating-dominating sets in restricted graph classes ⋮ Smooth kinetic maintenance of clusters ⋮ EFFICIENT DISTRIBUTED ALGORITHMS FOR TOPOLOGY CONTROL PROBLEM WITH SHORTEST PATH CONSTRAINTS ⋮ Dominating set of rectangles intersecting a straight line ⋮ Local PTAS for Dominating and Connected Dominating Set in Location Aware Unit Disk Graphs ⋮ A $(2 - c \frac{\log {n}}{n})$ Approximation Algorithm for the Minimum Maximal Matching Problem ⋮ Improper coloring of unit disk graphs ⋮ Fast and Simple Local Algorithms for 2-Edge Dominating Sets and 3-Total Vertex Covers ⋮ Approximation algorithms for the connected sensor cover problem ⋮ Local Algorithms for Dominating and Connected Dominating Sets of Unit Disk Graphs with Location Aware Nodes ⋮ Domination in Geometric Intersection Graphs ⋮ A \(5+\varepsilon\)-approximation algorithm for minimum weighted dominating set in unit disk graph ⋮ ANALYSIS ON THEORETICAL BOUNDS FOR APPROXIMATING DOMINATING SET PROBLEMS ⋮ A note on maximum independent sets and minimum clique partitions in unit disk graphs and penny graphs: complexity and approximation ⋮ Unnamed Item ⋮ Large independent sets in random regular graphs ⋮ A better constant-factor approximation for weighted dominating set in unit disk graph ⋮ A PTAS for Weak Minimum Routing Cost Connected Dominating Set of Unit Disk Graph ⋮ Finding, hitting and packing cycles in subexponential time on unit disk graphs ⋮ Unnamed Item ⋮ Parallel approximation schemes for a class of planar and near planar combinatorial optimization problems. ⋮ On-line coloring of geometric intersection graphs ⋮ A 2-approximation algorithm for the minimum weight edge dominating set problem ⋮ On full Steiner trees in unit disk graphs ⋮ On connected dominating sets of restricted diameter
This page was built for publication: NC-Approximation Schemes for NP- and PSPACE-Hard Problems for Geometric Graphs
