Fast subexponential algorithm for non-local problems on graphs of bounded genus

Frederic Dorn; Fedor V. Fomin; Dimitrios M. Thilikos

doi:10.1007/11785293_18

Fast subexponential algorithm for non-local problems on graphs of bounded genus

Frederic Dorn, Fedor V. Fomin, Dimitrios M. Thilikos

Computer Science

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

Abstract

We give a general technique for designing fast subexponential algorithms for several graph problems whose instances are restricted to graphs of bounded genus. We use it to obtain time 2^O(√n) algorithms for a wide family of problems such as HAMILTONIAN CYCLE, Σ-EMBEDDED GRAPH TRAVELLING SALESMAN PROBLEM, LONGEST CYCLE, and MAX LEAF TREE. For our results, we combine planarizing techniques with dynamic programming on special type branch decompositions. Our techniques can also be used to solve parameterized problems. Thus, for example, we show how to find a cycle of length p (or to conclude that there is no such a cycle) on graphs of bounded genus in time 2 ^O(√p).n^O(1)

Original language	English (US)
Title of host publication	Biomedical Simulation - Third International Symposium, ISBMS 2006, Proceedings
Publisher	Springer Verlag
Pages	172-183
Number of pages	12
ISBN (Print)	354035753X, 9783540357537
DOIs	https://doi.org/10.1007/11785293_18
State	Published - 2006
Event	10th Scandinavian Workshop on Algorithm Theory, SWAT 2006 - Riga, Latvia Duration: Jul 6 2006 → Jul 8 2006

Publication series

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

Conference

Conference	10th Scandinavian Workshop on Algorithm Theory, SWAT 2006
Country/Territory	Latvia
City	Riga
Period	7/6/06 → 7/8/06

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

Access to Document

10.1007/11785293_18

Cite this

Dorn, F., Fomin, F. V., & Thilikos, D. M. (2006). Fast subexponential algorithm for non-local problems on graphs of bounded genus. In Biomedical Simulation - Third International Symposium, ISBMS 2006, Proceedings (pp. 172-183). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 4059 LNCS). Springer Verlag. https://doi.org/10.1007/11785293_18

Fast subexponential algorithm for non-local problems on graphs of bounded genus. / Dorn, Frederic; Fomin, Fedor V.; Thilikos, Dimitrios M.
Biomedical Simulation - Third International Symposium, ISBMS 2006, Proceedings. Springer Verlag, 2006. p. 172-183 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 4059 LNCS).

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

Dorn, F, Fomin, FV & Thilikos, DM 2006, Fast subexponential algorithm for non-local problems on graphs of bounded genus. in Biomedical Simulation - Third International Symposium, ISBMS 2006, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 4059 LNCS, Springer Verlag, pp. 172-183, 10th Scandinavian Workshop on Algorithm Theory, SWAT 2006, Riga, Latvia, 7/6/06. https://doi.org/10.1007/11785293_18

Dorn F, Fomin FV, Thilikos DM. Fast subexponential algorithm for non-local problems on graphs of bounded genus. In Biomedical Simulation - Third International Symposium, ISBMS 2006, Proceedings. Springer Verlag. 2006. p. 172-183. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/11785293_18

Dorn, Frederic ; Fomin, Fedor V. ; Thilikos, Dimitrios M. / Fast subexponential algorithm for non-local problems on graphs of bounded genus. Biomedical Simulation - Third International Symposium, ISBMS 2006, Proceedings. Springer Verlag, 2006. pp. 172-183 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{3806369adf434bc6bff32732d7d070f9,

title = "Fast subexponential algorithm for non-local problems on graphs of bounded genus",

abstract = "We give a general technique for designing fast subexponential algorithms for several graph problems whose instances are restricted to graphs of bounded genus. We use it to obtain time 2O(√n) algorithms for a wide family of problems such as HAMILTONIAN CYCLE, Σ-EMBEDDED GRAPH TRAVELLING SALESMAN PROBLEM, LONGEST CYCLE, and MAX LEAF TREE. For our results, we combine planarizing techniques with dynamic programming on special type branch decompositions. Our techniques can also be used to solve parameterized problems. Thus, for example, we show how to find a cycle of length p (or to conclude that there is no such a cycle) on graphs of bounded genus in time 2 O(√p).nO(1)",

author = "Frederic Dorn and Fomin, {Fedor V.} and Thilikos, {Dimitrios M.}",

year = "2006",

doi = "10.1007/11785293_18",

language = "English (US)",

isbn = "354035753X",

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

publisher = "Springer Verlag",

pages = "172--183",

booktitle = "Biomedical Simulation - Third International Symposium, ISBMS 2006, Proceedings",

note = "10th Scandinavian Workshop on Algorithm Theory, SWAT 2006 ; Conference date: 06-07-2006 Through 08-07-2006",

}

TY - GEN

T1 - Fast subexponential algorithm for non-local problems on graphs of bounded genus

AU - Dorn, Frederic

AU - Fomin, Fedor V.

AU - Thilikos, Dimitrios M.

PY - 2006

Y1 - 2006

N2 - We give a general technique for designing fast subexponential algorithms for several graph problems whose instances are restricted to graphs of bounded genus. We use it to obtain time 2O(√n) algorithms for a wide family of problems such as HAMILTONIAN CYCLE, Σ-EMBEDDED GRAPH TRAVELLING SALESMAN PROBLEM, LONGEST CYCLE, and MAX LEAF TREE. For our results, we combine planarizing techniques with dynamic programming on special type branch decompositions. Our techniques can also be used to solve parameterized problems. Thus, for example, we show how to find a cycle of length p (or to conclude that there is no such a cycle) on graphs of bounded genus in time 2 O(√p).nO(1)

AB - We give a general technique for designing fast subexponential algorithms for several graph problems whose instances are restricted to graphs of bounded genus. We use it to obtain time 2O(√n) algorithms for a wide family of problems such as HAMILTONIAN CYCLE, Σ-EMBEDDED GRAPH TRAVELLING SALESMAN PROBLEM, LONGEST CYCLE, and MAX LEAF TREE. For our results, we combine planarizing techniques with dynamic programming on special type branch decompositions. Our techniques can also be used to solve parameterized problems. Thus, for example, we show how to find a cycle of length p (or to conclude that there is no such a cycle) on graphs of bounded genus in time 2 O(√p).nO(1)

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

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

U2 - 10.1007/11785293_18

DO - 10.1007/11785293_18

M3 - Conference contribution

AN - SCOPUS:33746433091

SN - 354035753X

SN - 9783540357537

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

SP - 172

EP - 183

BT - Biomedical Simulation - Third International Symposium, ISBMS 2006, Proceedings

PB - Springer Verlag

T2 - 10th Scandinavian Workshop on Algorithm Theory, SWAT 2006

Y2 - 6 July 2006 through 8 July 2006

ER -

Fast subexponential algorithm for non-local problems on graphs of bounded genus

Abstract

Publication series

Conference

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this