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

Ignasi Sau 1, * Dimitrios M. Thilikos 2
* Auteur correspondant
1 ALGCO - Algorithmes, Graphes et Combinatoire
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : We present subexponential parameterized algorithms on planar graphs for a family of problems of the following shape: given a graph, find a connected (induced) subgraph with bounded maximum degree and with maximum number of edges (or vertices). These problems are natural generalisations of the Longest Path problem. Our approach uses bidimensionality theory combined with novel dynamic programming techniques over branch decompositions of the input graph. These techniques can be applied to a more general family of problems that deal with finding connected subgraphs under certain degree constraints.
Type de document :
Article dans une revue
Journal of Discrete Algorithms, Elsevier, 2010, 8 (3), pp.330-338. 〈10.1016/j.jda.2010.02.002〉
Liste complète des métadonnées

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00736490
Contributeur : Ignasi Sau <>
Soumis le : vendredi 28 septembre 2012 - 12:22:31
Dernière modification le : jeudi 11 janvier 2018 - 06:26:13

Lien texte intégral

Identifiants

Collections

Citation

Ignasi Sau, Dimitrios M. Thilikos. Subexponential parameterized algorithms for degree-constrained subgraph problems on planar graphs. Journal of Discrete Algorithms, Elsevier, 2010, 8 (3), pp.330-338. 〈10.1016/j.jda.2010.02.002〉. 〈lirmm-00736490〉

Partager

Métriques

Consultations de la notice

108