Approximation algorithms for intersection graphs
From MaRDI portal
Signed and weighted graphs (05C22) Graph representations (geometric and intersection representations, etc.) (05C62) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Graph operations (line graphs, products, etc.) (05C76) Graph algorithms (graph-theoretic aspects) (05C85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)
Recommendations
Cites work
- 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 dominating set in disk graphs: breaking the \(\log n\) barrier (extended abstract)
- Algorithms for Minimum Coloring, Maximum Clique, Minimum Covering by Cliques, and Maximum Independent Set of a Chordal Graph
- 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
- 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?)
- 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
(27)- Co-bipartite neighborhood edge elimination orderings
- Approximation algorithms for classes of graphs excluding single-crossing graphs as minors
- Avoidable vertices and edges in graphs: existence, characterization, and applications
- On independent set in \(B_1\)-EPG graphs
- Hardness and approximation for L-EPG and \(B_1\)-EPG graphs
- Independent sets in Line of Sight networks
- Computing inductive vertex orderings
- The maximum clique problem in multiple interval graphs
- 1-perfectly orientable \(K_4\)-minor-free and outerplanar graphs
- Algorithms for graphs embeddable with few crossings per edge
- Hadwiger's conjecture and squares of chordal graphs
- Approximation hardness of optimization problems in intersection graphs of d-dimensional boxes
- Approximation algorithms for intersection graphs
- scientific article; zbMATH DE number 3904590 (Why is no real title available?)
- Algorithmic Aspects of the Intersection and Overlap Numbers of a Graph
- 1-perfectly orientable \(K_{4}\)-minor-free and outerplanar graphs
- \(1\)-perfectly orientable graphs and graph products
- Partial characterizations of 1-perfectly orientable graphs
- scientific article; zbMATH DE number 7071225 (Why is no real title available?)
- Intersection Algorithms and CAGD
- Fundamentals of Computation Theory
- Effective Wireless Scheduling via Hypergraph Sketches
- Induced minor models. I: Structural properties and algorithmic consequences
- Parameterized complexity of path set packing
- Algorithms and bounds for very strong rainbow coloring
- Detecting \(K_{2,3}\) as an induced minor
- Generalized disk graphs
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)
