Approximation Algorithms for Geometric Intersection Graphs
DOI10.1007/978-3-540-74839-7_15zbMATH Open1141.68536OpenAlexW2136451944MaRDI QIDQ3508563FDOQ3508563
Publication date: 1 July 2008
Published in: Graph-Theoretic Concepts in Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-540-74839-7_15
Recommendations
- Polynomial-Time Approximation Schemes for Geometric Intersection Graphs
- Polynomial-time approximation schemes for geometric graphs
- Graph-Theoretic Concepts in Computer Science
- Efficient independent set approximation in unit disk graphs
- Polynomial Time Approximation Schemes for MAX-BISECTION on Planar and Geometric Graphs
Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25) Graph representations (geometric and intersection representations, etc.) (05C62)
Cites Work
- Unit disk graphs
- Polynomial time approximation schemes for dense instances of \( \mathcal{NP}\)-hard problems
- Approximation algorithms for NP-complete problems on planar graphs
- Some simplified NP-complete graph problems
- Polynomial Time Approximation Schemes for MAX-BISECTION on Planar and Geometric Graphs
- NC-Approximation Schemes for NP- and PSPACE-Hard Problems for Geometric Graphs
- Finding a Maximum Cut of a Planar Graph in Polynomial Time
- Simple heuristics for unit disk graphs
- Title not available (Why is that?)
- Label placement by maximum independent set in rectangles
- Polynomial-Time Approximation Schemes for Geometric Intersection Graphs
- MAX-CUT and MAX-BISECTION are NP-hard on unit disk graphs
- Representing graphs by disks and balls (a survey of recognition-complexity results)
Cited In (17)
- Title not available (Why is that?)
- Polynomial-Time Approximation Schemes for Geometric Intersection Graphs
- Efficient Algorithms for Geometric Graph Search Problems
- Better Approximation Schemes for Disk Graphs
- Polynomial-time approximation schemes for geometric graphs
- Spanners for geometric intersection graphs with applications
- Title not available (Why is that?)
- Tractabilities and intractabilities on geometric intersection graphs
- NC-Approximation Schemes for NP- and PSPACE-Hard Problems for Geometric Graphs
- Polynomial Time Approximation Schemes for MAX-BISECTION on Planar and Geometric Graphs
- Domination in Geometric Intersection Graphs
- Intersection Algorithms and CAGD
- Algorithmic Aspects of the Intersection and Overlap Numbers of a Graph
- Geometric Intersection Graphs: Do Short Cycles Help?
- Independent set of intersection graphs of convex objects in 2D
- Title not available (Why is that?)
- Graph-Theoretic Concepts in Computer Science
This page was built for publication: Approximation Algorithms for Geometric Intersection Graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3508563)
