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

Ignasi Sau, Dimitrios M. Thilikos

Research output: Contribution to journalArticlepeer-review

Abstract

We present subexponential parameterized algorithms on planar graphs for a family of problems that consist in, given a graph G, finding a connected (induced) subgraph H with bounded maximum degree, while maximising the number of edges (or vertices) of H. These problems are natural generalisations of Longest Path. 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.

Original languageEnglish (US)
Pages (from-to)59-66
Number of pages8
JournalElectronic Notes in Discrete Mathematics
Volume32
Issue numberC
DOIs
StatePublished - Mar 15 2009

Keywords

  • bidimensionality
  • branch decomposition
  • Catalan structures
  • graph minors
  • Parameterized complexity
  • planar graphs
  • subexponential algorithm

ASJC Scopus subject areas

  • Discrete Mathematics and Combinatorics
  • Applied Mathematics

Fingerprint

Dive into the research topics of 'Subexponential Parameterized Algorithms for Bounded-Degree Connected Subgraph Problems on Planar Graphs'. Together they form a unique fingerprint.

Cite this