A framework for exponential-time-hypothesis-tight algorithms and lower bounds in geometric intersection graphs
From MaRDI portal
Publication:3387760
Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Analysis of algorithms (68W40) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Nonnumerical algorithms (68W05) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Graph representations (geometric and intersection representations, etc.) (05C62)
Recommendations
- A framework for ETH-tight algorithms and lower bounds in geometric intersection graphs
- Subexponential-time algorithms for Maximum Independent Set and related problems on box graphs
- Optimality program in segment and string graphs
- Optimality program in segment and string graphs
- The limited blessing of low dimensionality: when \(1-1/d\) is the best possible exponent for \(d\)-dimensional geometric problems (extended abstract)
Cites work
- scientific article; zbMATH DE number 3848625 (Why is no real title available?)
- scientific article; zbMATH DE number 3569818 (Why is no real title available?)
- scientific article; zbMATH DE number 1953201 (Why is no real title available?)
- scientific article; zbMATH DE number 7053376 (Why is no real title available?)
- A Separator Theorem for Planar Graphs
- A \(c^k n\) 5-approximation algorithm for treewidth
- A framework for ETH-tight algorithms and lower bounds in geometric intersection graphs
- A partial k-arboretum of graphs with bounded treewidth
- A simplified NP-complete satisfiability problem
- An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
- Applications of a Planar Separator Theorem
- Approximation algorithms for polynomial-expansion and low-density graphs
- Complexity and approximation results for the connected vertex cover problem in graphs and hypergraphs
- Computing the treewidth and the minimum fill-in with the modular decomposition
- Contraction-bidimensionality of geometric intersection graphs
- Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth
- ETH-Tight Algorithms for Long Path and Cycle on Unit Disk Graphs
- Finding, hitting and packing cycles in subexponential time on unit disk graphs
- Fine-grained complexity of coloring unit disks and balls
- Geometric separation and exact solutions for the parameterized independent set problem on disk graphs
- Graph minors. XIII: The disjoint paths problem
- Hamilton Paths in Grid Graphs
- Improved bounds for the union of locally fat objects in the plane
- Linear time solvable optimization problems on graphs of bounded clique-width
- Lower Bounds for Dominating Set in Ball Graphs and for Weighted Dominating Set in Unit-Ball Graphs
- On the clique-width of some perfect graph classes
- On the complexity of \(k\)-SAT
- On the exact complexity of Hamiltonian Cycle and \(q\)-Colouring in disk graphs
- Parameterized algorithms
- Planar Formulae and Their Uses
- Rank-width: algorithmic and structural results
- Safe reduction rules for weighted treewidth
- Sorting on a mesh-connected parallel computer
- Sphere and dot product representations of graphs
- The NP-completeness of the Hamiltonian cycle problem in planar digraphs with degree bound two
- The Pathwidth and Treewidth of Cographs
- The Planar Hamiltonian Circuit Problem is NP-Complete
- The Rectilinear Steiner Tree Problem is $NP$-Complete
- The complexity of dominating set in geometric intersection graphs
- The limited blessing of low dimensionality: when \(1-1/d\) is the best possible exponent for \(d\)-dimensional geometric problems (extended abstract)
- Theory and application of width bounded geometric separators
- Tree decompositions with small cost
- Unit disk graph recognition is NP-hard
- Unit disk graphs
- Which problems have strongly exponential complexity?
Cited in
(10)- Faster 3-coloring of small-diameter graphs
- Faster algorithms for cycle hitting problems on disk graphs
- Computing list homomorphisms in geometric intersection graphs
- A note on reachability and distance oracles for transmission graphs
- Fair allocation algorithms for indivisible items under structured conflict constraints
- Algorithms and Turing kernels for detecting and counting small patterns in unit disk graphs
- Geometric Intersection Graphs: Do Short Cycles Help?
- Clique-based separators for geometric intersection graphs
- An ETH-Tight Exact Algorithm for Euclidean TSP
- A framework for ETH-tight algorithms and lower bounds in geometric intersection graphs
This page was built for publication: A framework for exponential-time-hypothesis-tight algorithms and lower bounds in geometric intersection graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3387760)
