Approximation hardness of optimization problems in intersection graphs of d-dimensional boxes
From MaRDI portal
Approximation hardness of optimization problems in intersection graphs of \(d\)-dimensional boxes
Recommendations
- The Complexity of Combinatorial Optimization Problems on d‐Dimensional Boxes
- The hardness of approximating the boxicity, cubicity and threshold dimension of a graph
- Extremal Results on Intersection Graphs of Boxes in $${\mathbb R}^d$$ R d
- Approximation algorithms for intersection graphs
- Approximation algorithms for intersection graphs
- Sublinear approximation algorithms for boxicity and related problems
- Polynomial time and parameterized approximation algorithms for boxicity
- scientific article; zbMATH DE number 4142090
- On the inapproximability of maximum intersection problems
- Approximability of hard combinatorial optimization problems: an introduction
Cited in
(11)- Competitive algorithms for multistage online scheduling
- Scheduling split intervals with non-uniform demands
- Subexponential-time algorithms for Maximum Independent Set and related problems on box graphs
- Improved approximation algorithms for box contact representations
- Extremal Results on Intersection Graphs of Boxes in $${\mathbb R}^d$$ R d
- Approximating the Maximum Independent Set and Minimum Vertex Coloring on Box Graphs
- The Complexity of Combinatorial Optimization Problems on d‐Dimensional Boxes
- Minimum vertex cover in rectangle graphs
- The hardness of approximating the boxicity, cubicity and threshold dimension of a graph
- Temporal interval cliques and independent sets
- A note on maximum independent set and related problems on box graphs
This page was built for publication: Approximation hardness of optimization problems in intersection graphs of \(d\)-dimensional boxes
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2921679)
