Subexponential Parameterized Algorithms for Bounded-Degree Connected Subgraph Problems on Planar Graphs - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Communication Dans Un Congrès Année : 2009

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

Résumé

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.
Fichier non déposé

Dates et versions

hal-00795284 , version 1 (27-02-2013)

Identifiants

  • HAL Id : hal-00795284 , version 1

Citer

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. pp.59-66. ⟨hal-00795284⟩
43 Consultations
0 Téléchargements

Partager

Gmail Facebook X LinkedIn More