Approximation algorithms for intersection graphs
From MaRDI portal
Graph algorithms (graph-theoretic aspects) (05C85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Signed and weighted graphs (05C22) Graph representations (geometric and intersection representations, etc.) (05C62) Graph operations (line graphs, products, etc.) (05C76)
Recommendations
Cites work
- scientific article; zbMATH DE number 3859178 (Why is no real title available?)
- scientific article; zbMATH DE number 3513839 (Why is no real title available?)
- scientific article; zbMATH DE number 3593613 (Why is no real title available?)
- scientific article; zbMATH DE number 2065154 (Why is no real title available?)
- scientific article; zbMATH DE number 1507224 (Why is no real title available?)
- scientific article; zbMATH DE number 2230206 (Why is no real title available?)
- scientific article; zbMATH DE number 2234775 (Why is no real title available?)
- A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
- A Strongly Polynomial Algorithm to Solve Combinatorial Linear Programs
- A Weakly Robust PTAS for Minimum Clique Partition in Unit Disk Graphs
- Algorithmic aspects of intersection graphs and representation hypergraphs
- Algorithms for Minimum Coloring, Maximum Clique, Minimum Covering by Cliques, and Maximum Independent Set of a Chordal Graph
- Algorithms for dominating set in disk graphs: breaking the \(\log n\) barrier (extended abstract)
- Approximating minimum independent dominating sets in wireless networks
- Approximation algorithms for intersection graphs
- Approximation schemes for wireless networks
- Domination in Geometric Intersection Graphs
- Elimination Graphs
- Extremal Values of the Interval Number of a Graph
- Finding the connected components and a maximum clique of an intersection graph of rectangles in the plane
- Linear degree extractors and the inapproximability of max clique and chromatic number
- Minimum clique partition in unit disk graphs
- NC-Approximation Schemes for NP- and PSPACE-Hard Problems for Geometric Graphs
- Optimal packing and covering in the plane are NP-complete
- Optimization problems in multiple-interval graphs
- Optimization, approximation, and complexity classes
- Parameterized complexity in multiple-interval graphs: partition, separation, irredundancy
- Parametrized complexity theory.
- Polynomial-Time Approximation Schemes for Geometric Intersection Graphs
- Polynomial-time approximation schemes for packing and piercing fat objects
- Randomized graph products, chromatic numbers, and the Lovász \(\vartheta\)-function
- Scheduling Split Intervals
- Simple heuristics for unit disk graphs
- Some simplified NP-complete graph problems
- The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
- Tolerance intersection graphs on binary trees with constant tolerance 3
- Unit disk graphs
Cited in
(23)- Generalized disk graphs
- Partial characterizations of 1-perfectly orientable graphs
- scientific article; zbMATH DE number 3904590 (Why is no real title available?)
- Effective Wireless Scheduling via Hypergraph Sketches
- Computing inductive vertex orderings
- Approximation hardness of optimization problems in intersection graphs of \(d\)-dimensional boxes
- Approximation algorithms for intersection graphs
- Intersection Algorithms and CAGD
- Algorithmic Aspects of the Intersection and Overlap Numbers of a Graph
- On independent set in \(B_1\)-EPG graphs
- Approximation algorithms for classes of graphs excluding single-crossing graphs as minors
- Hadwiger's conjecture and squares of chordal graphs
- The maximum clique problem in multiple interval graphs
- Avoidable vertices and edges in graphs: existence, characterization, and applications
- Co-bipartite neighborhood edge elimination orderings
- Hardness and approximation for L-EPG and \(B_1\)-EPG graphs
- Algorithms for graphs embeddable with few crossings per edge
- 1-perfectly orientable \(K_4\)-minor-free and outerplanar graphs
- 1-perfectly orientable \(K_{4}\)-minor-free and outerplanar graphs
- scientific article; zbMATH DE number 7071225 (Why is no real title available?)
- Fundamentals of Computation Theory
- Independent sets in Line of Sight networks
- \(1\)-perfectly orientable graphs and graph products
This page was built for publication: Approximation algorithms for intersection graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q476425)
