Known Algorithms on Graphs of Bounded Treewidth Are Probably Optimal
From MaRDI portal
Publication:4554340
DOI10.1145/3170442zbMath1454.68110arXiv1007.5450OpenAlexW2800485060MaRDI QIDQ4554340
Daniel Lokshtanov, Saket Saurabh, Dániel Marx
Publication date: 13 November 2018
Published in: ACM Transactions on Algorithms (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1007.5450
Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items (24)
Structural parameterizations of clique coloring ⋮ Structural parameterization for minimum conflict-free colouring ⋮ Parameterized orientable deletion ⋮ Grundy Distinguishes Treewidth from Pathwidth ⋮ Solving cut-problems in quadratic time for graphs with bounded treewidth ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Finer Tight Bounds for Coloring on Clique-Width ⋮ Lower Bounds for Dynamic Programming on Planar Graphs of Bounded Cutwidth ⋮ Path Contraction Faster than $2^n$ ⋮ List \(k\)-colouring \(P_t\)-free graphs: a mim-width perspective ⋮ Generalized feedback vertex set problems on bounded-treewidth graphs: chordality is the key to single-exponential parameterized algorithms ⋮ On the parameterized complexity of \([1,j\)-domination problems] ⋮ A (probably) optimal algorithm for \textsc{bisection} on bounded-treewidth graphs ⋮ Parameterized Complexity of Conflict-Free Graph Coloring ⋮ On the complexity of finding large odd induced subgraphs and odd colorings ⋮ Path Contraction Faster Than 2^n ⋮ Structurally parameterized \(d\)-scattered set ⋮ Upper dominating set: tight algorithms for pathwidth and sub-exponential approximation ⋮ Upper dominating set: tight algorithms for pathwidth and sub-exponential approximation ⋮ Finding Hamiltonian Cycle in Graphs of Bounded Treewidth ⋮ Computing the chromatic number using graph decompositions via matrix rank ⋮ Fine-Grained Complexity of the Graph Homomorphism Problem for Bounded-Treewidth Graphs
This page was built for publication: Known Algorithms on Graphs of Bounded Treewidth Are Probably Optimal
