Hierarchically specified unit disk graphs
From MaRDI portal
Publication:1269904
DOI10.1016/S0304-3975(96)00008-4zbMath0908.68120OpenAlexW1973511353MaRDI QIDQ1269904
S. S. Ravi, Venkatesh Radhakrishnan, Madhav V. Marathe, Harry B. III Hunt
Publication date: 22 October 1998
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/s0304-3975(96)00008-4
Related Items
On Radiocoloring Hierarchically Specified Planar Graphs: $$\mathcal{PSPACE}$$ -completeness and Approximations ⋮ Model-checking hierarchical structures ⋮ Fixpoint logics over hierarchical structures
Cites Work
- Efficient solutions of hierarchical systems of linear equations
- A study on two geometric location problems
- Optimal packing and covering in the plane are NP-complete
- Unit disk graphs
- The correlation between the complexities of the nonhierarchical and hierarchical versions of graph problems
- Approximation schemes for PSPACE-complete problems for succinct specifications (preliminary version)
- On the Complexity of Some Common Geometric Location Problems
- Efficient algorithms for finding minimum spanning forests of hierarchically defined graphs
- Approximation schemes for covering and packing problems in image processing and VLSI
- Efficient Solution of Connectivity Problems on Hierarchically Defined Graphs
- On the hardness of approximating minimization problems
- Simple heuristics for unit disk graphs
- Hierarchical planarity testing algorithms
- Probabilistically checkable debate systems and approximation algorithms for PSPACE-hard functions
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
