Approximation algorithms for intersection graphs
DOI10.1007/s00453-012-9671-1zbMath1303.05193OpenAlexW2081642180WikidataQ56019096 ScholiaQ56019096MaRDI QIDQ476425
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
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
Cites Work
- 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
- Optimization problems in multiple-interval 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