Skip to Main content Skip to Navigation
Journal articles

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

Ignasi Sau Valls 1, * Dimitrios M. Thilikos 2
* Corresponding author
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.
Document type :
Journal articles
Complete list of metadata

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00736490
Contributor : Ignasi Sau <>
Submitted on : Friday, September 28, 2012 - 12:22:31 PM
Last modification on : Thursday, November 26, 2020 - 4:00:02 PM

Links full text

Identifiers

Collections

Citation

Ignasi Sau Valls, 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⟩

Share

Metrics

Record views

247