Better Approximation Schemes for Disk Graphs

DOI10.1007/11785293_30MaRDI QIDQ5757904zbMATH OpenOpenAlexFDO

Authors Erik Jan van Leeuwen

Publication date 7 September 2007

Published in Algorithm Theory – SWAT 2006 (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/11785293_30

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Recommendations

• Polynomial-time approximation schemes for geometric graphs
• Polynomial-Time Approximation Schemes for Geometric Intersection Graphs
• Graph-Theoretic Concepts in Computer Science
• Approximation Algorithms for Geometric Intersection Graphs
• Graph-Theoretic Concepts in Computer Science

Cited in

(15)

• Better approximations of non-Hamiltonian graphs
• Optimization problems in dotted interval graphs
• Polynomial-Time Approximation Schemes for Geometric Intersection Graphs
• Minimum vertex cover in rectangle graphs
• Polynomial-time approximation schemes for geometric graphs
• The MST of symmetric disk graphs is light
• Plane hop spanners for unit disk graphs: simpler and better
• The number of bits needed to represent a unit disk graph
• MAX-CUT and MAX-BISECTION are NP-hard on unit disk graphs
• Domination in Geometric Intersection Graphs
• Approximate Distance Queries in Disk Graphs
• A new characterization of disk graphs and its application.
• Algorithms – ESA 2005
• Global Rigidity of Unit Ball Graphs
• Structure of polynomial-time approximation

This page was built for publication: Better Approximation Schemes for Disk Graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5757904)