Catalan structures and dynamic programming in \(H\)-minor-free graphs
From MaRDI portal
Publication:440008
DOI10.1016/j.jcss.2012.02.004zbMath1244.05215WikidataQ60488458 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
68Q25: Analysis of algorithms and problem complexity
90C39: Dynamic programming
05C83: Graph minors
05C85: Graph algorithms (graph-theoretic aspects)
Related Items
Packing Cycles Faster Than Erdos--Posa, New analysis and computational study for the planar connected dominating set problem, Beyond bidimensionality: parameterized subexponential algorithms on directed graphs, Complete binary trees embeddings in Möbius cubes, Fixed-parameter algorithms for rectilinear Steiner tree and rectilinear traveling salesman problem in the plane, Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth, The role of planarity in connectivity problems parameterized by treewidth, Planar k-Path in Subexponential Time and Polynomial Space
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
