The role of planarity in connectivity problems parameterized by treewidth
From MaRDI portal
Publication:2514121
DOI10.1016/j.tcs.2014.12.010zbMath1306.05123arXiv1312.2889MaRDI QIDQ2514121
Publication date: 30 January 2015
Published in: Theoretical Computer Science, Parameterized and Exact Computation (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1312.2889
dynamic programmingplanar graphstreewidthparameterized complexityconnectivity problemssingle-exponential algorithms
68Q25: Analysis of algorithms and problem complexity
90C39: Dynamic programming
05C10: Planar graphs; geometric and topological aspects of graph theory
05C40: Connectivity
68Q27: Parameterized complexity, tractability and kernelization
Related Items
Unnamed Item, Unnamed Item, Efficient Graph Minors Theory and Parameterized Algorithms for (Planar) Disjoint Paths, Lower Bounds for Dynamic Programming on Planar Graphs of Bounded Cutwidth, Hitting minors on bounded treewidth graphs. III. Lower bounds
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Catalan structures and dynamic programming in \(H\)-minor-free graphs
- Graph minors. X: Obstructions to tree-decomposition
- Some simplified NP-complete graph problems
- Call routing and the ratcatcher
- Which problems have strongly exponential complexity?
- Efficient exact algorithms on planar graphs: Exploiting sphere cut decompositions
- Parametrized complexity theory.
- Sur les partitions non croisées d'un cycle. (The non-crossed partitions of a cycle)
- Robotic-cell scheduling: special polynomially solvable cases of the traveling salesman problem on permuted Monge matrices
- The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
- Dynamic Programming for H-minor-free Graphs
- Problems Parameterized by Treewidth Tractable in Single Exponential Time: A Logical Approach
- New upper bounds on the decomposability of planar graphs
- Graph minors. II. Algorithmic aspects of tree-width
- Deterministic Single Exponential Time Algorithms for Connectivity Problems Parameterized by Treewidth
- Efficient Computation of Representative Sets with Applications in Parameterized and Exact Algorithms
- Multiplying matrices faster than coppersmith-winograd
- Dynamic Programming and Fast Matrix Multiplication
- Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time
- Dynamic programming for graphs on surfaces
- Fast Subexponential Algorithm for Non-local Problems on Graphs of Bounded Genus