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

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) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

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

(17)

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

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)