Dominating Sets and Local Treewidth

Fedor V. Fomin; Dimtirios M. Thilikos

doi:10.1007/978-3-540-39658-1_22

Dominating Sets and Local Treewidth

Fedor V. Fomin, Dimtirios M. Thilikos

Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Chapter

Abstract

It is known that the treewidth of a planar graph with a dominating set of size d is O(√d) and this fact is used as the basis for several fixed parameter algorithms on planar graphs. An interesting question motivating our study is if similar bounds can be obtained for larger minor closed graph families. We say that a graph family F has the domination-treewidth property if there is some function f(d) such that every graph G ∈ F with dominating set of size ≤ d has treewidth ≤ f(d). We show that a minor-closed graph family F has the domination-treewidth property if and only if F has bounded local treewidth. This result has important algorithmic consequences.

Original language	English (US)
Title of host publication	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Editors	Giuseppe di Battista, Uri Zwick
Publisher	Springer Verlag
Pages	221-229
Number of pages	9
ISBN (Print)	3540200649, 9783540200642
DOIs	https://doi.org/10.1007/978-3-540-39658-1_22
State	Published - 2003

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	2832
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

Access to Document

10.1007/978-3-540-39658-1_22

Cite this

Fomin, F. V., & Thilikos, D. M. (2003). Dominating Sets and Local Treewidth. In G. di Battista, & U. Zwick (Eds.), Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) (pp. 221-229). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 2832). Springer Verlag. https://doi.org/10.1007/978-3-540-39658-1_22

Dominating Sets and Local Treewidth. / Fomin, Fedor V.; Thilikos, Dimtirios M.
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). ed. / Giuseppe di Battista; Uri Zwick. Springer Verlag, 2003. p. 221-229 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 2832).

Research output: Chapter in Book/Report/Conference proceeding › Chapter

Fomin, FV & Thilikos, DM 2003, Dominating Sets and Local Treewidth. in G di Battista & U Zwick (eds), Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 2832, Springer Verlag, pp. 221-229. https://doi.org/10.1007/978-3-540-39658-1_22

Fomin FV, Thilikos DM. Dominating Sets and Local Treewidth. In di Battista G, Zwick U, editors, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). Springer Verlag. 2003. p. 221-229. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-540-39658-1_22

Fomin, Fedor V. ; Thilikos, Dimtirios M. / Dominating Sets and Local Treewidth. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). editor / Giuseppe di Battista ; Uri Zwick. Springer Verlag, 2003. pp. 221-229 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inbook{a4fd2070862f4e6ca4b72c3b5343364b,

title = "Dominating Sets and Local Treewidth",

abstract = "It is known that the treewidth of a planar graph with a dominating set of size d is O(√d) and this fact is used as the basis for several fixed parameter algorithms on planar graphs. An interesting question motivating our study is if similar bounds can be obtained for larger minor closed graph families. We say that a graph family F has the domination-treewidth property if there is some function f(d) such that every graph G ∈ F with dominating set of size ≤ d has treewidth ≤ f(d). We show that a minor-closed graph family F has the domination-treewidth property if and only if F has bounded local treewidth. This result has important algorithmic consequences.",

author = "Fomin, {Fedor V.} and Thilikos, {Dimtirios M.}",

year = "2003",

doi = "10.1007/978-3-540-39658-1_22",

language = "English (US)",

isbn = "3540200649",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "221--229",

editor = "{di Battista}, Giuseppe and Uri Zwick",

booktitle = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

}

TY - CHAP

T1 - Dominating Sets and Local Treewidth

AU - Fomin, Fedor V.

AU - Thilikos, Dimtirios M.

PY - 2003

Y1 - 2003

N2 - It is known that the treewidth of a planar graph with a dominating set of size d is O(√d) and this fact is used as the basis for several fixed parameter algorithms on planar graphs. An interesting question motivating our study is if similar bounds can be obtained for larger minor closed graph families. We say that a graph family F has the domination-treewidth property if there is some function f(d) such that every graph G ∈ F with dominating set of size ≤ d has treewidth ≤ f(d). We show that a minor-closed graph family F has the domination-treewidth property if and only if F has bounded local treewidth. This result has important algorithmic consequences.

AB - It is known that the treewidth of a planar graph with a dominating set of size d is O(√d) and this fact is used as the basis for several fixed parameter algorithms on planar graphs. An interesting question motivating our study is if similar bounds can be obtained for larger minor closed graph families. We say that a graph family F has the domination-treewidth property if there is some function f(d) such that every graph G ∈ F with dominating set of size ≤ d has treewidth ≤ f(d). We show that a minor-closed graph family F has the domination-treewidth property if and only if F has bounded local treewidth. This result has important algorithmic consequences.

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

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

U2 - 10.1007/978-3-540-39658-1_22

DO - 10.1007/978-3-540-39658-1_22

M3 - Chapter

AN - SCOPUS:0142152737

SN - 3540200649

SN - 9783540200642

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 221

EP - 229

BT - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

A2 - di Battista, Giuseppe

A2 - Zwick, Uri

PB - Springer Verlag

ER -

Dominating Sets and Local Treewidth

Abstract

Publication series

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this