TY - GEN

T1 - Subexponential parameterized algorithms

AU - Dorn, Frederic

AU - Fomin, Fedor V.

AU - Thilikos, Dimitrios M.

PY - 2007

Y1 - 2007

N2 - We present a series of techniques for the design of subexponential parameterized algorithms for graph problems. The design of such algorithms usually consists of two main steps: first find a branch- (or tree-) decomposition of the input graph whose width is bounded by a sublinear function of the parameter and, second, use this decomposition to solve the problem in time that is single exponential to this bound. The main tool for the first step is Bidimensionality Theory. Here we present the potential, but also the boundaries, of this theory. For the second step, we describe recent techniques, associating the analysis of sub-exponential algorithms to combinatorial bounds related to Catalan numbers. As a result, we have 2 o(√k)·no(1) time algorithms for a wide variety of parameterized problems on graphs, where n is the size of the graph and k is the parameter.

AB - We present a series of techniques for the design of subexponential parameterized algorithms for graph problems. The design of such algorithms usually consists of two main steps: first find a branch- (or tree-) decomposition of the input graph whose width is bounded by a sublinear function of the parameter and, second, use this decomposition to solve the problem in time that is single exponential to this bound. The main tool for the first step is Bidimensionality Theory. Here we present the potential, but also the boundaries, of this theory. For the second step, we describe recent techniques, associating the analysis of sub-exponential algorithms to combinatorial bounds related to Catalan numbers. As a result, we have 2 o(√k)·no(1) time algorithms for a wide variety of parameterized problems on graphs, where n is the size of the graph and k is the parameter.

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

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

U2 - 10.1007/978-3-540-73420-8_4

DO - 10.1007/978-3-540-73420-8_4

M3 - Conference contribution

AN - SCOPUS:38149120277

SN - 3540734198

SN - 9783540734192

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

SP - 15

EP - 27

BT - Automata, Languages and Programming - 34th International Colloquium, ICALP 2007, Proceedings

PB - Springer Verlag

T2 - 34th International Colloquium on Automata, Languages and Programming, ICALP 2007

Y2 - 9 July 2007 through 13 July 2007

ER -