NC-Approximation Schemes for NP- and PSPACE-Hard Problems for Geometric Graphs
From MaRDI portal
Publication:4386448
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
(89)- A \(5+\varepsilon\)-approximation algorithm for minimum weighted dominating set in unit disk graph
- Large independent sets in random regular graphs
- A better constant-factor approximation for weighted dominating set in unit disk graph
- Hierarchically specified unit disk graphs
- A 2-approximation algorithm for the minimum weight edge dominating set problem
- On approximating (connected) 2-edge dominating set by a tree
- Impact of locality on location aware unit disk graphs
- Smooth kinetic maintenance of clusters
- Parallel approximation schemes for a class of planar and near planar combinatorial optimization problems.
- On-line coloring of geometric intersection graphs
- Approximation algorithms for finding and partitioning unit-disk graphs into co-k-plexes
- Decision and approximation complexity for identifying codes and locating-dominating sets in restricted graph classes
- Dominating set of rectangles intersecting a straight line
- Parallel algorithm for minimum partial dominating set in unit disk graph
- A linear-time algorithm for minimum \(k\)-hop dominating set of a cactus graph
- A polynomial-time approximation to a minimum dominating set in a graph
- Efficient independent set approximation in unit disk graphs
- Dispersing and grouping points on planar segments
- Minimum vertex cover in ball graphs through local search
- Finding, hitting and packing cycles in subexponential time on unit disk graphs
- On full Steiner trees in unit disk graphs
- On connected dominating sets of restricted diameter
- Degree-constrained decompositions of graphs: Bounded treewidth and planarity
- Approximability of identifying codes and locating-dominating codes
- Efficient sub-5 approximations for minimum dominating sets in unit disk graphs
- Improper colouring of (random) unit disk graphs
- Packing triangles in low degree graphs and indifference graphs
- Polynomial-time approximation schemes for piercing and covering with applications in wireless networks
- Independent set of intersection graphs of convex objects in 2D
- Parallel algorithms for minimum general partial dominating set and maximum budgeted dominating set in unit disk graph
- 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
- Improper coloring of unit disk graphs
- A note on maximum independent sets and minimum clique partitions in unit disk graphs and penny graphs: complexity and approximation
- A parallel hybrid greedy branch and bound scheme for the maximum distance-2 matching problem
- A PTAS for the Weighted Unit Disk Cover Problem
- Consensus patterns (probably) has no EPTAS
- Linear-time approximation algorithms for unit disk graphs
- On Radiocoloring Hierarchically Specified Planar Graphs: $$\mathcal{PSPACE}$$ -completeness and Approximations
- Maximum independent set on \(B_1\)-VPG graphs
- Approximation Algorithms for Geometric Intersection Graphs
- ROMAN DOMINATION AND ITS VARIANTS IN UNIT DISK GRAPHS
- 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
- ANALYSIS ON THEORETICAL BOUNDS FOR APPROXIMATING DOMINATING SET PROBLEMS
- On approximating string selection problems with outliers
- Optimization problems in dotted interval graphs
- Algorithms for the minimum weight k-fold (connected) dominating set problem
- scientific article; zbMATH DE number 2081090 (Why is no real title available?)
- Shifting strategy for geometric graphs without geometry
- Shifting coresets: obtaining linear-time approximations for unit disk graphs and other geometric intersection graphs
- Approximation algorithms for intersection graphs
- POINT SET LABELING WITH SPECIFIED POSITIONS
- Efficient distributed algorithms for topology control problem with shortest path constraints
- A PTAS for weak minimum routing cost connected dominating set of unit disk graph
- The within-strip discrete unit disk cover problem
- On connected domination in unit ball graphs
- Local Algorithms for Dominating and Connected Dominating Sets of Unit Disk Graphs with Location Aware Nodes
- Domination in Geometric Intersection Graphs
- Minimum vertex cover in rectangle graphs
- DISTRIBUTED SPANNERS WITH BOUNDED DEGREE FOR WIRELESS AD HOC NETWORKS
- scientific article; zbMATH DE number 2230206 (Why is no real title available?)
- On approximating (connected) 2-edge dominating set by a tree
- scientific article; zbMATH DE number 7053376 (Why is no real title available?)
- PTAS for Sparse General-valued CSPs
- Distributed connected dominating sets in unit square and disk graphs
- Polynomial time approximation schemes for minimum disk cover problems
- Theory and application of width bounded geometric separators
- Analysing local algorithms in location-aware quasi-unit-disk graphs
- Minimum-membership geometric dominating set: complexity and algorithms
- Approximation of MWIS on geometric intersection graphs
- Computing diameter+2 in truly-subquadratic time for unit-disk graphs
- Fully dynamic maximum independent sets of disks in polylogarithmic update time
- Structure of polynomial-time approximation
- Partial domination in some geometric intersection graphs
- An improved PTAS for covering targets with mobile sensors
- Contraction decomposition in unit disk graphs and algorithmic applications in parameterized complexity
- Pliability and approximating Max-CSPs
- Improved approximation algorithms for 2-dimensional knapsack: packing into multiple l-shapes, spirals, and more
- Shortest path separators in unit disk graphs
- Fully dynamic maximum independent sets of disks in polylogarithmic update time
- A QPTAS for facility location on unit disk graphs
- On pseudo-disk hypergraphs
- The connected domination number of grids
- Randomized on-line algorithms and lower bounds for computing large independent sets in disk graphs
- MAX-CUT and MAX-BISECTION are NP-hard on unit disk graphs
- A polynomial-time approximation scheme for the geometric unique coverage problem on unit squares
- On the complexity of bandwidth allocation in radio networks
- Approximating minimum independent dominating sets in wireless networks
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)
