Subexponential parameterized algorithms for degree-constrained subgraph problems on planar graphs - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier
Article Dans Une Revue Journal of Discrete Algorithms Année : 2010

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

Résumé

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.

Dates et versions

lirmm-00736490 , version 1 (28-09-2012)

Identifiants

Citer

Ignasi Sau, Dimitrios M. Thilikos. Subexponential parameterized algorithms for degree-constrained subgraph problems on planar graphs. Journal of Discrete Algorithms, 2010, 8 (3), pp.330-338. ⟨10.1016/j.jda.2010.02.002⟩. ⟨lirmm-00736490⟩
111 Consultations
0 Téléchargements

Altmetric

Partager

More