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

Ignasi Sau; Dimitrios M. Thilikos

doi:10.1016/j.endm.2009.02.009

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

Ignasi Sau, Dimitrios M. Thilikos

Computer Science

Research output: Contribution to journal › Article › peer-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 language	English (US)
Pages (from-to)	59-66
Number of pages	8
Journal	Electronic Notes in Discrete Mathematics
Volume	32
Issue number	C
DOIs	https://doi.org/10.1016/j.endm.2009.02.009
State	Published - 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

Access to Document

10.1016/j.endm.2009.02.009

Cite this

@article{35194564b9704f67b0f79e8b46ad6dcc,

title = "Subexponential Parameterized Algorithms for Bounded-Degree Connected Subgraph Problems on Planar Graphs",

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.",

keywords = "bidimensionality, branch decomposition, Catalan structures, graph minors, Parameterized complexity, planar graphs, subexponential algorithm",

author = "Ignasi Sau and Thilikos, {Dimitrios M.}",

year = "2009",

month = mar,

day = "15",

doi = "10.1016/j.endm.2009.02.009",

language = "English (US)",

volume = "32",

pages = "59--66",

journal = "Electronic Notes in Discrete Mathematics",

issn = "1571-0653",

publisher = "Elsevier",

number = "C",

}

TY - JOUR

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

AU - Sau, Ignasi

AU - Thilikos, Dimitrios M.

PY - 2009/3/15

Y1 - 2009/3/15

N2 - 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.

AB - 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.

KW - bidimensionality

KW - branch decomposition

KW - Catalan structures

KW - graph minors

KW - Parameterized complexity

KW - planar graphs

KW - subexponential algorithm

UR - http://www.scopus.com/inward/record.url?scp=61549132311&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=61549132311&partnerID=8YFLogxK

U2 - 10.1016/j.endm.2009.02.009

DO - 10.1016/j.endm.2009.02.009

M3 - Article

AN - SCOPUS:61549132311

SN - 1571-0653

VL - 32

SP - 59

EP - 66

JO - Electronic Notes in Discrete Mathematics

JF - Electronic Notes in Discrete Mathematics

IS - C

ER -

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

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this