Subexponential parameterized algorithms for degree-constrained subgraph problems on planar graphs

DOI10.1016/j.jda.2010.02.002zbMath1192.90239OpenAlexW2016465035MaRDI QIDQ988694

Dimitrios M. Thilikos, Ignasi Sau

Publication date: 18 August 2010

Published in: Journal of Discrete Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jda.2010.02.002

zbMATH Keywords

planar graphsparameterized complexitygraph minorssubexponential algorithmbidimensionalitybranch decompositionCatalan structures

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35)

Related Items (12)

Subexponential Parameterized Algorithms for Planar and Apex-Minor-Free Graphs via Low Treewidth Pattern Covering ⋮ On Computing the Hamiltonian Index of Graphs ⋮ Fixed-Parameter Tractability of Treewidth and Pathwidth ⋮ Unnamed Item ⋮ Parameterized complexity of finding small degree-constrained subgraphs ⋮ Catalan structures and dynamic programming in \(H\)-minor-free graphs ⋮ On computing the Hamiltonian index of graphs ⋮ On the approximability of some degree-constrained subgraph problems ⋮ Faster parameterized algorithms for minor containment ⋮ Confronting intractability via parameters ⋮ Induced packing of odd cycles in planar graphs ⋮ Dynamic programming for graphs on surfaces

Cites Work

• Semi-nice tree-decompositions: the best of branchwidth, treewidth and pathwidth with one algorithm
• Matching theory
• Graph minors. X: Obstructions to tree-decomposition
• Call routing and the ratcatcher
• Quickly excluding a planar graph
• Parametrized complexity theory.
• Sur les partitions non croisées d'un cycle. (The non-crossed partitions of a cycle)
• New upper bounds on the decomposability of planar graphs
• Dominating Sets in Planar Graphs: Branch-Width and Exponential Speed-Up
• Subexponential parameterized algorithms on bounded-genus graphs and H -minor-free graphs
• Degree-Constrained Subgraph Problems: Hardness and Approximation Results
• Constant-Factor Approximations of Branch-Decomposition and Largest Grid Minor of Planar Graphs in O(n 1 + ε ) Time
• Supereulerian graphs: A survey
• Optimal branch-decomposition of planar graphs in O ( n ³ ) Time
• Subexponential Parameterized Algorithms
• Algorithms – ESA 2005
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Subexponential parameterized algorithms for degree-constrained subgraph problems on planar graphs