Better Approximation Schemes for Disk Graphs

DOI10.1007/11785293_30zbMath1142.68617OpenAlexW2099021285MaRDI QIDQ5757904

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

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

Related Items (7)

MAX-CUT and MAX-BISECTION are NP-hard on unit disk graphs ⋮ Optimization problems in dotted interval graphs ⋮ Structure of polynomial-time approximation ⋮ Minimum vertex cover in rectangle graphs ⋮ The Number of Bits Needed to Represent a Unit Disk Graph ⋮ Domination in Geometric Intersection Graphs ⋮ Global Rigidity of Unit Ball Graphs

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