A Framework for Exponential-Time-Hypothesis--Tight Algorithms and Lower Bounds in Geometric Intersection Graphs (Q3387760): Difference between revisions

@@ Property / cites work @@
+Geometric separation and exact solutions for the parameterized independent set problem on disk graphs
+Normal rank
@@ Property / cites work @@
+Improved Bounds for the Union of Locally Fat Objects in the Plane
+Normal rank
@@ Property / cites work @@
+Contraction-Bidimensionality of Geometric Intersection Graphs
+Normal rank
@@ Property / cites work @@
+A framework for ETH-tight algorithms and lower bounds in geometric intersection graphs
+Normal rank
@@ Property / cites work @@
+Lower Bounds for Dominating Set in Ball Graphs and for Weighted Dominating Set in Unit-Ball Graphs
+Normal rank
@@ Property / cites work @@
+The complexity of dominating set in geometric intersection graphs
+Normal rank
@@ Property / cites work @@
+Q4626304
@@ Property / cites work: Q4626304 / rank @@
+Normal rank
@@ Property / cites work @@
+A partial k-arboretum of graphs with bounded treewidth
+Normal rank
@@ Property / cites work @@
+Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth
+Normal rank
@@ Property / cites work @@
+A $c^k n$ 5-Approximation Algorithm for Treewidth
@@ Property / cites work: A $c^k n$ 5-Approximation Algorithm for Treewidth / rank @@
+Normal rank
@@ Property / cites work @@
+Tree decompositions with small cost
@@ Property / cites work: Tree decompositions with small cost / rank @@
+Normal rank
@@ Property / cites work @@
+The Pathwidth and Treewidth of Cographs
@@ Property / cites work: The Pathwidth and Treewidth of Cographs / rank @@
+Normal rank
@@ Property / cites work @@
+Computing the treewidth and the minimum fill-in with the modular decomposition
+Normal rank
@@ Property / cites work @@
+Unit disk graph recognition is NP-hard
@@ Property / cites work: Unit disk graph recognition is NP-hard / rank @@
+Normal rank
@@ Property / cites work @@
+Unit disk graphs
@@ Property / cites work: Unit disk graphs / rank @@
+Normal rank
@@ Property / cites work @@
+Linear time solvable optimization problems on graphs of bounded clique-width
+Normal rank
@@ Property / cites work @@
+Parameterized Algorithms
@@ Property / cites work: Parameterized Algorithms / rank @@
+Normal rank
@@ Property / cites work @@
+Complexity and approximation results for the connected vertex cover problem in graphs and hypergraphs
+Normal rank
@@ Property / cites work @@
+Finding, Hitting and Packing Cycles in Subexponential Time on Unit Disk Graphs
+Normal rank
@@ Property / cites work @@
+ETH-Tight Algorithms for Long Path and Cycle on Unit Disk Graphs
+Normal rank
@@ Property / cites work @@
+Q5743499
@@ Property / cites work: Q5743499 / rank @@
+Normal rank
@@ Property / cites work @@
+Theory and application of width bounded geometric separators
+Normal rank
@@ Property / cites work @@
+The Rectilinear Steiner Tree Problem is $NP$-Complete
+Normal rank
@@ Property / cites work @@
+The Planar Hamiltonian Circuit Problem is NP-Complete
+Normal rank
@@ Property / cites work @@
+ON THE CLIQUE-WIDTH OF SOME PERFECT GRAPH CLASSES
@@ Property / cites work: ON THE CLIQUE-WIDTH OF SOME PERFECT GRAPH CLASSES / rank @@
+Normal rank
@@ Property / cites work @@
+Approximation Algorithms for Polynomial-Expansion and Low-Density Graphs
+Normal rank
@@ Property / cites work @@
+An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
+Normal rank
@@ Property / cites work @@
+On the complexity of \(k\)-SAT
@@ Property / cites work: On the complexity of \(k\)-SAT / rank @@
+Normal rank
@@ Property / cites work @@
+Which problems have strongly exponential complexity?
+Normal rank
@@ Property / cites work @@
+Hamilton Paths in Grid Graphs
@@ Property / cites work: Hamilton Paths in Grid Graphs / rank @@
+Normal rank
@@ Property / cites work @@
+Sphere and dot product representations of graphs
@@ Property / cites work: Sphere and dot product representations of graphs / rank @@
+Normal rank
@@ Property / cites work @@
+Nearly ETH-tight Algorithms for Planar Steiner Tree with Terminals on Few Faces
+Normal rank
@@ Property / cites work @@
+On the Exact Complexity of Hamiltonian Cycle and q-Colouring in Disk Graphs
+Normal rank
@@ Property / cites work @@
+Planar Formulae and Their Uses
@@ Property / cites work: Planar Formulae and Their Uses / rank @@
+Normal rank
@@ Property / cites work @@
+A Separator Theorem for Planar Graphs
@@ Property / cites work: A Separator Theorem for Planar Graphs / rank @@
+Normal rank
@@ Property / cites work @@
+Applications of a Planar Separator Theorem
@@ Property / cites work: Applications of a Planar Separator Theorem / rank @@
+Normal rank
@@ Property / cites work @@
+Optimal Parameterized Algorithms for Planar Facility Location Problems Using Voronoi Diagrams
+Normal rank
@@ Property / cites work @@
+The limited blessing of low dimensionality
@@ Property / cites work: The limited blessing of low dimensionality / rank @@
+Normal rank
@@ Property / cites work @@
+Rank-width: algorithmic and structural results
@@ Property / cites work: Rank-width: algorithmic and structural results / rank @@
+Normal rank
@@ Property / cites work @@
+The NP-completeness of the Hamiltonian cycle problem in planar digraphs with degree bound two
+Normal rank
@@ Property / cites work @@
+Graph minors. XIII: The disjoint paths problem
@@ Property / cites work: Graph minors. XIII: The disjoint paths problem / rank @@
+Normal rank
@@ Property / cites work @@
+Q3318125
@@ Property / cites work: Q3318125 / rank @@
+Normal rank
@@ Property / cites work @@
+Q4140370
@@ Property / cites work: Q4140370 / rank @@
+Normal rank
@@ Property / cites work @@
+Sorting on a mesh-connected parallel computer
@@ Property / cites work: Sorting on a mesh-connected parallel computer / rank @@
+Normal rank
@@ Property / cites work @@
+A simplified NP-complete satisfiability problem
@@ Property / cites work: A simplified NP-complete satisfiability problem / rank @@
+Normal rank
@@ Property / cites work @@
+Safe reduction rules for weighted treewidth
@@ Property / cites work: Safe reduction rules for weighted treewidth / rank @@
+Normal rank
@@ Property / cites work @@
+Q4414647
@@ Property / cites work: Q4414647 / rank @@
+Normal rank
@@ Property / full work available at URL @@
+https://doi.org/10.1137/20m1320870
+Normal rank
@@ Property / OpenAlex ID @@
+W3112807772
@@ Property / OpenAlex ID: W3112807772 / rank @@
+Normal rank