Problems Parameterized by Treewidth Tractable in Single Exponential Time: A Logical Approach
From MaRDI portal
Publication:3088068
DOI10.1007/978-3-642-22993-0_47zbMath1343.68120arXiv1104.3057OpenAlexW1493923326MaRDI QIDQ3088068
Publication date: 17 August 2011
Published in: Mathematical Foundations of Computer Science 2011 (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1104.3057
Analysis of algorithms and problem complexity (68Q25) Modal logic (including the logic of norms) (03B45) Specification and verification (program logics, model checking, etc.) (68Q60) Complexity of computation (including implicit computational complexity) (03D15)
Related Items (23)
Contraction bidimensionality of geometric intersection graphs ⋮ Unnamed Item ⋮ Hitting forbidden subgraphs in graphs of bounded treewidth ⋮ Linear kernels for outbranching problems in sparse digraphs ⋮ Parameterized complexity dichotomy for \((r, \ell)\)-\textsc{Vertex Deletion} ⋮ Simplified algorithmic metatheorems beyond MSO: treewidth and neighborhood diversity ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Catalan structures and dynamic programming in \(H\)-minor-free graphs ⋮ Unnamed Item ⋮ Contracting graphs to paths and trees ⋮ Lower Bounds for Dynamic Programming on Planar Graphs of Bounded Cutwidth ⋮ Slightly Superexponential Parameterized Problems ⋮ Unnamed Item ⋮ Subexponential parameterized algorithms and kernelization on almost chordal graphs ⋮ The role of planarity in connectivity problems parameterized by treewidth ⋮ Subexponential-time algorithms for finding large induced sparse subgraphs ⋮ Unnamed Item ⋮ Hitting forbidden induced subgraphs on bounded treewidth graphs ⋮ Hitting Forbidden Induced Subgraphs on Bounded Treewidth Graphs ⋮ Contraction-Bidimensionality of Geometric Intersection Graphs ⋮ Fine-Grained Complexity of the Graph Homomorphism Problem for Bounded-Treewidth Graphs ⋮ Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth
This page was built for publication: Problems Parameterized by Treewidth Tractable in Single Exponential Time: A Logical Approach
