NC-Approximation Schemes for NP- and PSPACE-Hard Problems for Geometric Graphs
From MaRDI portal
Publication:4386448
DOI10.1006/JAGM.1997.0903zbMATH Open0894.68105OpenAlexW2028738060MaRDI QIDQ4386448FDOQ4386448
Authors: V. Radhakrishnan, S. S. Ravi, R. E. Stearns, H. 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
Recommendations
- scientific article; zbMATH DE number 2081090
- Polynomial-time approximation schemes for geometric graphs
- Approximation schemes for NP-hard geometric optimization problems: a survey
- Hardness and approximation for the geodetic set problem in some graph classes
- Polynomial-Time Approximation Schemes for Geometric Intersection Graphs
- Approximation algorithms for NP-complete problems on planar graphs
- Approximation Algorithms for Geometric Intersection Graphs
- Geometric complexity theory. I: An approach to the P vs. NP and related problems
- On \textsf{NC} algorithms for problems on bounded rank-width graphs
- scientific article; zbMATH DE number 437554
Cited In (76)
- Consensus patterns (probably) has no EPTAS
- Finding, hitting and packing cycles in subexponential time on unit disk graphs
- Dispersing and grouping points on planar segments
- Fast and simple local algorithms for 2-edge dominating sets and 3-total vertex covers
- On the power of lookahead in greedy scheme for finding a minimum CDS for unit disk graphs
- PTAS for Sparse General-valued CSPs
- Shifting coresets: obtaining linear-time approximations for unit disk graphs and other geometric intersection graphs
- Linear-time approximation algorithms for unit disk graphs
- Distributed connected dominating sets in unit square and disk graphs
- Title not available (Why is that?)
- On approximating string selection problems with outliers
- Parallel approximation schemes for a class of planar and near planar combinatorial optimization problems.
- Optimization problems in dotted interval graphs
- On pseudo-disk hypergraphs
- The connected domination number of grids
- Improper colouring of (random) unit disk graphs
- Minimum vertex cover in rectangle graphs
- A polynomial-time approximation scheme for the geometric unique coverage problem on unit squares
- Polynomial-time approximation schemes for piercing and covering with applications in wireless networks
- ROMAN DOMINATION AND ITS VARIANTS IN UNIT DISK GRAPHS
- On full Steiner trees in unit disk graphs
- Local Algorithms for Dominating and Connected Dominating Sets of Unit Disk Graphs with Location Aware Nodes
- Improper coloring of unit disk graphs
- POINT SET LABELING WITH SPECIFIED POSITIONS
- A $(2 - c \frac{\log {n}}{n})$ Approximation Algorithm for the Minimum Maximal Matching Problem
- Efficient sub-5 approximations for minimum dominating sets in unit disk graphs
- A 2-approximation algorithm for the minimum weight edge dominating set problem
- DISTRIBUTED SPANNERS WITH BOUNDED DEGREE FOR WIRELESS AD HOC NETWORKS
- On approximating (connected) 2-edge dominating set by a tree
- On approximating (connected) 2-edge dominating set by a tree
- Dominating set of rectangles intersecting a straight line
- On connected domination in unit ball graphs
- Shifting strategy for geometric graphs without geometry
- A \(5+\varepsilon\)-approximation algorithm for minimum weighted dominating set in unit disk graph
- On-line coloring of geometric intersection graphs
- Decision and approximation complexity for identifying codes and locating-dominating sets in restricted graph classes
- Local PTAS for Dominating and Connected Dominating Set in Location Aware Unit Disk Graphs
- MAX-CUT and MAX-BISECTION are NP-hard on unit disk graphs
- Maximum independent set on \(B_1\)-VPG graphs
- Parallel algorithm for minimum partial dominating set in unit disk graph
- On connected dominating sets of restricted diameter
- Polynomial time approximation schemes for minimum disk cover problems
- Impact of locality on location aware unit disk graphs
- Approximation Algorithms for Geometric Intersection Graphs
- Title not available (Why is that?)
- A parallel hybrid greedy branch and bound scheme for the maximum distance-2 matching problem
- A better constant-factor approximation for weighted dominating set in unit disk graph
- Efficient independent set approximation in unit disk graphs
- Algorithms for the minimum weight \(k\)-fold (connected) dominating set problem
- Domination in Geometric Intersection Graphs
- Approximation algorithms for intersection graphs
- Theory and application of width bounded geometric separators
- A PTAS for the Weighted Unit Disk Cover Problem
- Parallel algorithms for minimum general partial dominating set and maximum budgeted dominating set in unit disk graph
- Large independent sets in random regular graphs
- Approximation algorithms for finding and partitioning unit-disk graphs into co-\(k\)-plexes
- Smooth kinetic maintenance of clusters
- ANALYSIS ON THEORETICAL BOUNDS FOR APPROXIMATING DOMINATING SET PROBLEMS
- Approximating minimum independent dominating sets in wireless networks
- Analysing local algorithms in location-aware quasi-unit-disk graphs
- On Radiocoloring Hierarchically Specified Planar Graphs: $$\mathcal{PSPACE}$$ -completeness and Approximations
- Degree-constrained decompositions of graphs: Bounded treewidth and planarity
- A note on maximum independent sets and minimum clique partitions in unit disk graphs and penny graphs: complexity and approximation
- Minimum vertex cover in ball graphs through local search
- A polynomial-time approximation to a minimum dominating set in a graph
- A linear-time algorithm for minimum \(k\)-hop dominating set of a cactus graph
- On the complexity of bandwidth allocation in radio networks
- Approximability of identifying codes and locating-dominating codes
- Independent set of intersection graphs of convex objects in 2D
- Randomized on-line algorithms and lower bounds for computing large independent sets in disk graphs
- Efficient distributed algorithms for topology control problem with shortest path constraints
- Packing triangles in low degree graphs and indifference graphs
- A PTAS for weak minimum routing cost connected dominating set of unit disk graph
- Structure of polynomial-time approximation
- Title not available (Why is that?)
- The within-strip discrete unit disk cover problem
This page was built for publication: NC-Approximation Schemes for NP- and PSPACE-Hard Problems for Geometric Graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4386448)
