Catalan structures and dynamic programming in \(H\)-minor-free graphs
From MaRDI portal
Publication:440008
DOI10.1016/j.jcss.2012.02.004zbMath1244.05215OpenAlexW2015321560WikidataQ60488458 ScholiaQ60488458MaRDI QIDQ440008
Frederic Dorn, Fedor V. Fomin, Dimitrios M. Thilikos
Publication date: 17 August 2012
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.jcss.2012.02.004
Analysis of algorithms and problem complexity (68Q25) Dynamic programming (90C39) Graph minors (05C83) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items
Subexponential Parameterized Algorithms for Planar and Apex-Minor-Free Graphs via Low Treewidth Pattern Covering ⋮ Four Shorts Stories on Surprising Algorithmic Uses of Treewidth ⋮ New analysis and computational study for the planar connected dominating set problem ⋮ Fixed-parameter algorithms for rectilinear Steiner tree and rectilinear traveling salesman problem in the plane ⋮ Beyond bidimensionality: parameterized subexponential algorithms on directed graphs ⋮ Complete binary trees embeddings in Möbius cubes ⋮ A \(2^{O(k)}n\) algorithm for \(k\)-cycle in minor-closed graph families ⋮ The role of planarity in connectivity problems parameterized by treewidth ⋮ Packing Cycles Faster Than Erdos--Posa ⋮ Planar k-Path in Subexponential Time and Polynomial Space ⋮ Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Subexponential parameterized algorithms
- Embeddings of graphs with no short noncontractible cycles
- Linearity of grid minors in treewidth with applications through bidimensionality
- Subexponential parameterized algorithms for degree-constrained subgraph problems on planar graphs
- Graph minors. VII: Disjoint paths on a surface
- Graph minors. XI: Circuits on a surface
- Call routing and the ratcatcher
- Graph minors. XVI: Excluding a non-planar graph
- Which problems have strongly exponential complexity?
- On limited nondeterminism and the complexity of the V-C dimension
- Fixed parameter algorithms for DOMINATING SET and related problems on planar graphs
- Efficient exact algorithms on planar graphs: Exploiting sphere cut decompositions
- Parametrized complexity theory.
- Exact algorithms for the Hamiltonian cycle problem in planar graphs
- Sur les partitions non croisées d'un cycle. (The non-crossed partitions of a cycle)
- Tour Merging via Branch-Decomposition
- Linear time low tree-width partitions and algorithmic consequences
- Problems Parameterized by Treewidth Tractable in Single Exponential Time: A Logical Approach
- Dominating Sets in Planar Graphs: Branch-Width and Exponential Speed-Up
- Subexponential parameterized algorithms on bounded-genus graphs and H -minor-free graphs
- A Linear-Time Approximation Scheme for TSP in Undirected Planar Graphs with Edge-Weights
- Dynamic Programming for Graphs on Surfaces
- Coloring a Family of Circular Arcs
- Color-coding
- Parameterized complexity: exponential speed-up for planar graph problems
- Optimal branch-decomposition of planar graphs in O ( n 3 ) Time
- Bidimensional Parameters and Local Treewidth
- A simpler algorithm and shorter proof for the graph minor decomposition
- Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time
- Fast Subexponential Algorithm for Non-local Problems on Graphs of Bounded Genus
