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

}