Hierarchically specified unit disk graphs

DOI10.1007/3-540-57899-4_38zbMath1528.68309MaRDI QIDQ6184390

S. S. Ravi, Harry B. III Hunt, Madhav V. Marathe, Venkatesh Radhakrishnan

Publication date: 5 January 2024

Published in: Graph-Theoretic Concepts in Computer Science (Search for Journal in Brave)

zbMATH Keywords

intersection graphpolynomial timevertex covermaximum clique problemunit disk graph

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Graph representations (geometric and intersection representations, etc.) (05C62)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• 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
• On the Complexity of Some Common Geometric Location Problems
• Succinct representations of graphs
• 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
• The complexity of approximating PSPACE-complete problems for hierarchical specifications
• Hierarchical planarity testing algorithms