Approximation algorithms for intersection graphs

DOI10.1007/s00453-012-9671-1zbMath1303.05193OpenAlexW2081642180WikidataQ56019096 ScholiaQ56019096MaRDI QIDQ476425

Torsten Tholey, Frank Kammer

Publication date: 2 December 2014

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-012-9671-1

zbMATH Keywords

graph algorithmsintersection graphsNP-hard problemsparameterized approximation algorithms

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Approximation algorithms (68W25) Graph representations (geometric and intersection representations, etc.) (05C62) Signed and weighted graphs (05C22) Graph operations (line graphs, products, etc.) (05C76)

Related Items (14)

Generalized disk graphs ⋮ On independent set in \(B_1\)-EPG graphs ⋮ 1-perfectly orientable \(K_4\)-minor-free and outerplanar graphs ⋮ Hardness and approximation for L-EPG and \(B_1\)-EPG graphs ⋮ Co-bipartite neighborhood edge elimination orderings ⋮ Independent sets in Line of Sight networks ⋮ Computing inductive vertex orderings ⋮ 1-perfectly orientable \(K_{4}\)-minor-free and outerplanar graphs ⋮ \(1\)-perfectly orientable graphs and graph products ⋮ Hadwiger’s Conjecture and Squares of Chordal Graphs ⋮ Avoidable vertices and edges in graphs: existence, characterization, and applications ⋮ Effective Wireless Scheduling via Hypergraph Sketches ⋮ The maximum clique problem in multiple interval graphs ⋮ Partial Characterizations of 1‐Perfectly Orientable Graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Minimum clique partition in unit disk graphs
• Approximating minimum independent dominating sets in wireless networks
• Algorithmic aspects of intersection graphs and representation hypergraphs
• Optimal packing and covering in the plane are NP-complete
• Unit disk graphs
• Optimization, approximation, and complexity classes
• Some simplified NP-complete graph problems
• Randomized graph products, chromatic numbers, and the Lovász \(\vartheta\)-function
• Tolerance intersection graphs on binary trees with constant tolerance 3
• Parametrized complexity theory.
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• A Strongly Polynomial Algorithm to Solve Combinatorial Linear Programs
• Parameterized Complexity in Multiple-Interval Graphs: Partition, Separation, Irredundancy
• Finding the connected components and a maximum clique of an intersection graph of rectangles in the plane
• A Weakly Robust PTAS for Minimum Clique Partition in Unit Disk Graphs
• Algorithms for Dominating Set in Disk Graphs: Breaking the logn Barrier
• Approximation Algorithms for Intersection Graphs
• Elimination Graphs
• Extremal Values of the Interval Number of a Graph
• NC-Approximation Schemes for NP- and PSPACE-Hard Problems for Geometric Graphs
• Simple heuristics for unit disk graphs
• Polynomial-time approximation schemes for packing and piercing fat objects
• Approximation schemes for wireless networks
• Polynomial-Time Approximation Schemes for Geometric Intersection Graphs
• Domination in Geometric Intersection Graphs
• Scheduling Split Intervals
• Algorithms for Minimum Coloring, Maximum Clique, Minimum Covering by Cliques, and Maximum Independent Set of a Chordal Graph
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth

This page was built for publication: Approximation algorithms for intersection graphs