Lower Bounds for Dynamic Programming on Planar Graphs of Bounded Cutwidth
DOI10.7155/jgaa.00542zbMath1446.05087OpenAlexW3095536655MaRDI QIDQ5131225
Bart M. P. Jansen, Arnoud A. W. M. de Kroon, Bas A. M. van Geffen, Rolf Morel
Publication date: 5 November 2020
Published in: Journal of Graph Algorithms and Applications (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.7155/jgaa.00542
Abstract computational complexity for mathematical programming problems (90C60) Dynamic programming (90C39) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items (1)
Cites Work
- Unnamed Item
- Unnamed Item
- Some simplified NP-complete graph problems
- A partial k-arboretum of graphs with bounded treewidth
- Which problems have strongly exponential complexity?
- Cutwidth: obstructions and algorithmic aspects
- Tree-width, path-width, and cutwidth
- Lower bounds for protrusion replacement by counting equivalence classes
- Computing the chromatic number using graph decompositions via matrix rank
- Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth
- The role of planarity in connectivity problems parameterized by treewidth
- The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
- Vertex Cover: Further Observations and Further Improvements
- Problems Parameterized by Treewidth Tractable in Single Exponential Time: A Logical Approach
- Efficient Computation of Representative Families with Applications in Parameterized and Exact Algorithms
- Fourier meets M\"{o}bius: fast subset convolution
- Dynamic Programming on Tree Decompositions Using Generalised Fast Subset Convolution
- Known Algorithms on Graphs of Bounded Treewidth Are Probably Optimal
- Fast Hamiltonicity Checking Via Bases of Perfect Matchings
- The Effect of Planarization on Width
- Hardness of Easy Problems: Basing Hardness on Popular Conjectures such as the Strong Exponential Time Hypothesis (Invited Talk)
- Cutwidth I: A linear time fixed parameter algorithm
- Cutwidth II: Algorithms for partial w-trees of bounded degree
- Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time
- On the complexity of \(k\)-SAT
This page was built for publication: Lower Bounds for Dynamic Programming on Planar Graphs of Bounded Cutwidth
