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

1 Dimitrios M. Thilikos
1 MASCOTTE - Algorithms, simulation, combinatorics and optimization for telecommunications
CRISAM - Inria Sophia Antipolis - Méditerranée , COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués
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 27 février 2013 - 17:09:23

Identifiants

  • HAL Id : hal-00795284, version 1

Collections

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

72