Subexponential Parameterized Algorithms for Bounded-Degree Connected Subgraph Problems on Planar Graphs

DOI10.1016/j.endm.2009.02.009zbMath1267.05271OpenAlexW2063956355MaRDI QIDQ2839212

Dimitrios M. Thilikos, Ignasi Sau

Publication date: 4 July 2013

Published in: Electronic Notes in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.endm.2009.02.009

zbMATH Keywords

planar graphsparameterized complexitygraph minorssubexponential algorithmbidimensionalitybranch decompositionCatalan structures

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (2)

An ILP formulation and genetic algorithm for the maximum degree-bounded connected subgraph problem ⋮ Subexponential Parameterized Algorithms for Bounded-Degree Connected Subgraph Problems on Planar Graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Matching theory
• 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)
• Subexponential Parameterized Algorithms for Bounded-Degree Connected Subgraph Problems on Planar Graphs
• New upper bounds on the decomposability of planar graphs
• Subexponential parameterized algorithms on bounded-genus graphs and H -minor-free graphs
• Degree-Constrained Subgraph Problems: Hardness and Approximation Results
• Optimal branch-decomposition of planar graphs in O ( n ³ ) Time
• Subexponential Parameterized Algorithms
• Algorithms – ESA 2005

This page was built for publication: Subexponential Parameterized Algorithms for Bounded-Degree Connected Subgraph Problems on Planar Graphs