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

Abstract : We present subexponential parameterized algorithms on planar graphs for a family of problems that consist in, given a graph $G$, finding a connected subgraph $H$ with bounded maximum degree, while maximising the number of edges (or vertices) of $H$. These problems are natural generalisations of the \\textscLongest Path problem. Our approach uses bidimensionality theory to obtain combinatorial bounds, combined with dynamic programming techniques over a branch decomposition of the input graph. These techniques need to be able to keep track of the connected components of the partial solutions over the branch decomposition, and can be seen as an \\emphalgorithmic tensor that can be applied to a wide family of problems that deal with finding connected subgraphs under certain constraints.
Type de document :
Communication dans un congrès
DIMAP workshop on Algorithmic Graph Theory (AGT09), 2009, Warwick, United Kingdom. Elsevier, 32, pp.59-66, 2009, Electronic Notes in Discrete Mathematics
Liste complète des métadonnées

https://hal.inria.fr/hal-00795284
Contributeur : Alain Monteil <>
Soumis le : mercredi 27 février 2013 - 17:09:23
Dernière modification le : mercredi 30 août 2017 - 01:11:08

Identifiants

  • HAL Id : hal-00795284, version 1

Citation

Dimitrios M. Thilikos. Subexponential Parameterized Algorithms for Bounded-Degree Connected Subgraph Problems on Planar Graphs. DIMAP workshop on Algorithmic Graph Theory (AGT09), 2009, Warwick, United Kingdom. Elsevier, 32, pp.59-66, 2009, Electronic Notes in Discrete Mathematics. 〈hal-00795284〉

Partager

Métriques

Consultations de la notice

81