Idioma:

Faster Parameterized Algorithms for Minor Containment

Adler, Isolde ; Dorn, Frederic ; Fomin, Fedor V. ; Sau, Ignasi ; Thilikos, Dimitrios M.

Algorithm Theory - SWAT 2010, p.322-333 [Periódico revisado por pares]

Berlin, Heidelberg: Springer Berlin Heidelberg

Sem texto completo

Citações Citado por

Enviar para

Título:
Faster Parameterized Algorithms for Minor Containment
Autor: Adler, Isolde ; Dorn, Frederic ; Fomin, Fedor V. ; Sau, Ignasi ; Thilikos, Dimitrios M.
Assuntos: branchwidth ; dynamic programming ; Graph minors ; graphs on surfaces ; parameterized complexity
É parte de: Algorithm Theory - SWAT 2010, p.322-333
Descrição: The theory of Graph Minors by Robertson and Seymour is one of the deepest and significant theories in modern Combinatorics. This theory has also a strong impact on the recent development of Algorithms, and several areas, like Parameterized Complexity, have roots in Graph Minors. Until very recently it was a common belief that Graph Minors Theory is mainly of theoretical importance. However, it appears that many deep results from Robertson and Seymour’s theory can be also used in the design of practical algorithms. Minor containment testing is one of algorithmically most important and technical parts of the theory, and minor containment in graphs of bounded branchwidth is a basic ingredient of this algorithm. In order to implement minor containment testing on graphs of bounded branchwidth, Hicks [NETWORKS 04] described an algorithm, that in time \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\mathcal{O}(3^{k^2}\cdot (h+k-1)!\cdot m)$\end{document} decides if a graph G with m edges and branchwidth k, contains a fixed graph H on h vertices as a minor. That algorithm follows the ideas introduced by Robertson and Seymour in [J’CTSB 95]. In this work we improve the dependence on k of Hicks’ result by showing that checking if H is a minor of G can be done in time \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\mathcal{O}(2^{(2k +1 )\cdot \log k} \cdot h^{2k} \cdot 2^{2h^2} \cdot m)$\end{document}. Our approach is based on a combinatorial object called rooted packing, which captures the properties of the potential models of subgraphs of H that we seek in our dynamic programming algorithm. This formulation with rooted packings allows us to speed up the algorithm when G is embedded in a fixed surface, obtaining the first single-exponential algorithm for minor containment testing. Namely, it runs in time \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$2^{\mathcal{O}(k)} \cdot h^{2k} \cdot 2^{\mathcal{O}(h)} \cdot n$\end{document}, with n = |V(G)|. Finally, we show that slight modifications of our algorithm permit to solve some related problems within the same time bounds, like induced minor or contraction minor containment.
Editor: Berlin, Heidelberg: Springer Berlin Heidelberg
Idioma: Inglês

Voltar para lista de resultados

Anterior Resultado 12 Avançar Ir para próxima página

Realização: Logos de Redes Sociais:

Faster Parameterized Algorithms for Minor Containment

Adler, Isolde ; Dorn, Frederic ; Fomin, Fedor V. ; Sau, Ignasi ; Thilikos, Dimitrios M.

Berlin, Heidelberg: Springer Berlin Heidelberg

Buscando em bases de dados remotas. Favor aguardar.