Contraction bidimensionality: The accurate picture

Fedor V. Fomin; Petr Golovach; Dimitrios M. Thilikos

doi:10.1007/978-3-642-04128-0_63

Contraction bidimensionality: The accurate picture

Fedor V. Fomin, Petr Golovach, Dimitrios M. Thilikos

Computer Science

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

Abstract

We provide new combinatorial theorems on the structure of graphs that are contained as contractions in graphs of large treewidth. As a consequence of our combinatorial results we unify and significantly simplify contraction bidimensionality theory-the meta algorithmic framework to design efficient parameterized and approximation algorithms for contraction closed parameters.

Original language	English (US)
Title of host publication	Algorithms - ESA 2009 - 17th Annual European Symposium, Proceedings
Pages	706-717
Number of pages	12
DOIs	https://doi.org/10.1007/978-3-642-04128-0_63
State	Published - 2009
Event	17th Annual European Symposium on Algorithms, ESA 2009 - Copenhagen, Denmark Duration: Sep 7 2009 → Sep 9 2009

Publication series

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

Conference

Conference	17th Annual European Symposium on Algorithms, ESA 2009
Country/Territory	Denmark
City	Copenhagen
Period	9/7/09 → 9/9/09

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

Access to Document

10.1007/978-3-642-04128-0_63

Cite this

Fomin, F. V., Golovach, P., & Thilikos, D. M. (2009). Contraction bidimensionality: The accurate picture. In Algorithms - ESA 2009 - 17th Annual European Symposium, Proceedings (pp. 706-717). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 5757 LNCS). https://doi.org/10.1007/978-3-642-04128-0_63

Contraction bidimensionality: The accurate picture. / Fomin, Fedor V.; Golovach, Petr; Thilikos, Dimitrios M.
Algorithms - ESA 2009 - 17th Annual European Symposium, Proceedings. 2009. p. 706-717 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 5757 LNCS).

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

Fomin, FV, Golovach, P & Thilikos, DM 2009, Contraction bidimensionality: The accurate picture. in Algorithms - ESA 2009 - 17th Annual European Symposium, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 5757 LNCS, pp. 706-717, 17th Annual European Symposium on Algorithms, ESA 2009, Copenhagen, Denmark, 9/7/09. https://doi.org/10.1007/978-3-642-04128-0_63

@inproceedings{539bcd01de9f4e61b66843d374850a72,

title = "Contraction bidimensionality: The accurate picture",

abstract = "We provide new combinatorial theorems on the structure of graphs that are contained as contractions in graphs of large treewidth. As a consequence of our combinatorial results we unify and significantly simplify contraction bidimensionality theory-the meta algorithmic framework to design efficient parameterized and approximation algorithms for contraction closed parameters.",

author = "Fomin, {Fedor V.} and Petr Golovach and Thilikos, {Dimitrios M.}",

year = "2009",

doi = "10.1007/978-3-642-04128-0_63",

language = "English (US)",

isbn = "3642041272",

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

pages = "706--717",

booktitle = "Algorithms - ESA 2009 - 17th Annual European Symposium, Proceedings",

note = "17th Annual European Symposium on Algorithms, ESA 2009 ; Conference date: 07-09-2009 Through 09-09-2009",

}

TY - GEN

T1 - Contraction bidimensionality

T2 - 17th Annual European Symposium on Algorithms, ESA 2009

AU - Fomin, Fedor V.

AU - Golovach, Petr

AU - Thilikos, Dimitrios M.

PY - 2009

Y1 - 2009

N2 - We provide new combinatorial theorems on the structure of graphs that are contained as contractions in graphs of large treewidth. As a consequence of our combinatorial results we unify and significantly simplify contraction bidimensionality theory-the meta algorithmic framework to design efficient parameterized and approximation algorithms for contraction closed parameters.

AB - We provide new combinatorial theorems on the structure of graphs that are contained as contractions in graphs of large treewidth. As a consequence of our combinatorial results we unify and significantly simplify contraction bidimensionality theory-the meta algorithmic framework to design efficient parameterized and approximation algorithms for contraction closed parameters.

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

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

U2 - 10.1007/978-3-642-04128-0_63

DO - 10.1007/978-3-642-04128-0_63

M3 - Conference contribution

AN - SCOPUS:70350401895

SN - 3642041272

SN - 9783642041273

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

SP - 706

EP - 717

BT - Algorithms - ESA 2009 - 17th Annual European Symposium, Proceedings

Y2 - 7 September 2009 through 9 September 2009

ER -

Contraction bidimensionality: The accurate picture

Abstract

Publication series

Conference

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this