Approximation Algorithms for Geometric Intersection Graphs

DOI10.1007/978-3-540-74839-7_15MaRDI QIDQ3508563zbMATH OpenOpenAlexFDO

Authors Klaus Jansen

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

Mathematics Subject Classification ID

Graph representations (geometric and intersection representations, etc.) (05C62) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25)

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

Cites work

• Approximation algorithms for NP-complete problems on planar graphs
• Finding a Maximum Cut of a Planar Graph in Polynomial Time
• scientific article; zbMATH DE number 3027510 (Why is no real title available?)
• Label placement by maximum independent set in rectangles
• MAX-CUT and MAX-BISECTION are NP-hard on unit disk graphs
• NC-Approximation Schemes for NP- and PSPACE-Hard Problems for Geometric Graphs
• Polynomial time approximation schemes for dense instances of \( \mathcal{NP}\)-hard problems
• Polynomial Time Approximation Schemes for MAX-BISECTION on Planar and Geometric Graphs
• Polynomial-Time Approximation Schemes for Geometric Intersection Graphs
• Representing graphs by disks and balls (a survey of recognition-complexity results)
• Simple heuristics for unit disk graphs
• Some simplified NP-complete graph problems
• Unit disk graphs

Cited in

(27)

• Tractabilities and intractabilities on geometric intersection graphs
• Independent set of intersection graphs of convex objects in 2D
• scientific article; zbMATH DE number 1688377 (Why is no real title available?)
• Polynomial-time approximation schemes for geometric graphs
• Spanners for geometric intersection graphs with applications
• scientific article; zbMATH DE number 2089217 (Why is no real title available?)
• scientific article; zbMATH DE number 437554 (Why is no real title available?)
• Maximum area independent sets in disk intersection graphs
• Approximation algorithms for intersection graphs
• Geometric Intersection Graphs: Do Short Cycles Help?
• Efficient Algorithms for Geometric Graph Search Problems
• NC-Approximation Schemes for NP- and PSPACE-Hard Problems for Geometric Graphs
• Approximation algorithms for maximum independent set of pseudo-disks
• Shifting strategy for geometric graphs without geometry
• Approximation algorithms for intersection graphs
• Algorithmic Aspects of the Intersection and Overlap Numbers of a Graph
• Algorithms for intersection graphs for \(t\)-intervals and \(t\)-pseudodisks
• Polynomial-Time Approximation Schemes for Geometric Intersection Graphs
• Computing the independence number of intersection graphs
• Intersection Algorithms and CAGD
• Domination in Geometric Intersection Graphs
• Polynomial Time Approximation Schemes for MAX-BISECTION on Planar and Geometric Graphs
• Graph-Theoretic Concepts in Computer Science
• Better Approximation Schemes for Disk Graphs
• Approximation algorithms for maximum matchings in geometric intersection graphs
• Maximum bipartite subgraphs of geometric intersection graphs
• Maximum bipartite subgraph of geometric intersection graphs

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)