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

Ignasi Sau; Dimitrios M. Thilikos

doi:10.1016/j.jda.2010.02.002

Subexponential parameterized algorithms for degree-constrained 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 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.

Original language	English (US)
Pages (from-to)	330-338
Number of pages	9
Journal	Journal of Discrete Algorithms
Volume	8
Issue number	3
DOIs	https://doi.org/10.1016/j.jda.2010.02.002
State	Published - Sep 2010

Keywords

Bidimensionality
Branch decomposition
Catalan structures
Graph minors
Parameterized complexity
Planar graphs
Subexponential algorithm

ASJC Scopus subject areas

Theoretical Computer Science
Discrete Mathematics and Combinatorics
Computational Theory and Mathematics

Access to Document

10.1016/j.jda.2010.02.002

Cite this

@article{7522cdf1d0f644ac820b6007374df88d,

title = "Subexponential parameterized algorithms for degree-constrained subgraph problems on planar graphs",

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

keywords = "Bidimensionality, Branch decomposition, Catalan structures, Graph minors, Parameterized complexity, Planar graphs, Subexponential algorithm",

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

year = "2010",

month = sep,

doi = "10.1016/j.jda.2010.02.002",

language = "English (US)",

volume = "8",

pages = "330--338",

journal = "Journal of Discrete Algorithms",

issn = "1570-8667",

publisher = "Elsevier",

number = "3",

}

TY - JOUR

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

AU - Sau, Ignasi

AU - Thilikos, Dimitrios M.

PY - 2010/9

Y1 - 2010/9

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

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

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=77955714305&partnerID=8YFLogxK

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

U2 - 10.1016/j.jda.2010.02.002

DO - 10.1016/j.jda.2010.02.002

M3 - Article

AN - SCOPUS:77955714305

SN - 1570-8667

VL - 8

SP - 330

EP - 338

JO - Journal of Discrete Algorithms

JF - Journal of Discrete Algorithms

IS - 3

ER -

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

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this