The role of planarity in connectivity problems parameterized by treewidth

DOI10.1016/j.tcs.2014.12.010zbMath1306.05123arXiv1312.2889OpenAlexW2183582012MaRDI 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

Analysis of algorithms and problem complexity (68Q25) Dynamic programming (90C39) Planar graphs; geometric and topological aspects of graph theory (05C10) Connectivity (05C40) Parameterized complexity, tractability and kernelization (68Q27)

Related Items (5)

Efficient Graph Minors Theory and Parameterized Algorithms for (Planar) Disjoint Paths ⋮ Unnamed Item ⋮ Unnamed Item ⋮ 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

This page was built for publication: The role of planarity in connectivity problems parameterized by treewidth