Hierarchically specified unit disk graphs
type: Item
instance of: scholarly article
title: Hierarchically specified unit disk graphs
zbMATH Open document ID: 0908.68120
DOI: 10.1016/S0304-3975(96)00008-4
author: Madhav V. Marathe
author: V. Radhakrishnan
author: H. B. III Hunt
author: S. S. Ravi
published in: Theoretical Computer Science
publication date: 1998-10-22T00:00:00Z
Mathematics Subject Classification ID: 68R10
zbMATH DE Number: 1213156
zbMATH Keywords: optimization problems
zbMATH Keywords: PSPACE-hardness
MaRDI profile type: Publication
cites work: Q4230322
cites work: Unit disk graphs
cites work: Probabilistically checkable debate systems and approximation algorithms for PSPACE-hard functions
cites work: Optimal packing and covering in the plane are NP-complete
cites work: Q4198056
cites work: Q4293540
cites work: Q4886045
cites work: Approximation schemes for covering and packing problems in image processing and VLSI
cites work: Q3140457
cites work: Efficient algorithms for finding minimum spanning forests of hierarchically defined graphs
cites work: Hierarchical planarity testing algorithms
cites work: The correlation between the complexities of the nonhierarchical and hierarchical versions of graph problems
cites work: Efficient Solution of Connectivity Problems on Hierarchically Defined Graphs
cites work: Efficient solutions of hierarchical systems of linear equations
cites work: On the hardness of approximating minimization problems
cites work: Simple heuristics for unit disk graphs
cites work: Q4764625
cites work: Approximation schemes for PSPACE-complete problems for succinct specifications (preliminary version)
cites work: Q4375760
cites work: On the Complexity of Some Common Geometric Location Problems
cites work: Q3338297
cites work: Q3340147
cites work: A study on two geometric location problems
full work available at URL: s0304-3975(96)00008-4
OpenAlex ID: W1973511353
description: scientific article; zbMATH DE number 1213156