Catalan structures and dynamic programming in \(H\)-minor-free graphs

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

zbMATH Keywords

longest pathparameterized complexityCatalan structureminor-free graphs

Mathematics Subject Classification ID

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 ³ ) 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