The role of planarity in connectivity problems parameterized by treewidth

DOI10.1016/j.tcs.2014.12.010zbMath1306.05123arXiv1312.2889MaRDI QIDQ2514121

Julien Baste, Ignasi Sau

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

zbMATH Keywords

dynamic programmingplanar graphstreewidthparameterized complexityconnectivity problemssingle-exponential algorithms

Mathematics Subject Classification ID

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