skip to main content
Idioma:
Primo Search
Clear Search Box
Search in: Busca Geral
Busca Avançada
Busca por Índices
Tipo de recurso Mostra resultados com: Mostra resultados com: Índice

Catalan structures and dynamic programming in H-minor-free graphs

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

Journal of computer and system sciences, 2012-09, Vol.78 (5), p.1606-1622 [Periódico revisado por pares]

Elsevier Inc

Texto completo disponível

Citações Citado por
  • Título:
    Catalan structures and dynamic programming in H-minor-free graphs
  • Autor: Dorn, Frederic ; Fomin, Fedor V. ; Thilikos, Dimitrios M.
  • Assuntos: Algorithms ; Catalan structure ; Combinatorial analysis ; Computer Science ; Construction ; Decomposition ; Discrete Mathematics ; Dynamical systems ; Dynamics ; Graphs ; Integers ; Longest path ; Minor-free graphs ; Parameterized complexity
  • É parte de: Journal of computer and system sciences, 2012-09, Vol.78 (5), p.1606-1622
  • Notas: ObjectType-Article-2
    SourceType-Scholarly Journals-1
    ObjectType-Feature-1
    content type line 23
  • Descrição: We give an algorithm that, for a fixed graph H and integer k, decides whether an n-vertex H-minor-free graph G contains a path of length k in 2O(k)⋅nO(1) steps. Our approach builds on a combination of Demaine–Hajiaghayiʼs bounds on the size of an excluded grid in such graphs with a novel combinatorial result on certain branch decompositions of H-minor-free graphs. This result is used to bound the number of ways vertex disjoint paths can be routed through the separators of such decompositions. The proof is based on several structural theorems from the Graph Minors series of Robertson and Seymour. With a slight modification, similar combinatorial and algorithmic results can be derived for many other problems. Our approach can be viewed as a general framework for obtaining time 2O(k)⋅nO(1) algorithms on H-minor-free graph classes. ► We give a 2O(k)⋅nO(1) algorithm for k-path problem on H-minor-free graphs. ► We combine known excluded grid and novel decomposition results on such graphs. ► This bounds the number of ways paths can be routed through decomposition separators. ► The proof is based on structural theorems from Graph Minors (Robertson and Seymour). ► Similar combinatorial and algorithmic results can be derived for many other problems.
  • Editor: Elsevier Inc
  • Idioma: Inglês
Links
Voltar para lista de resultados
Ir para página anteriorAnterior Resultado  2 AvançarIr para próxima página

  • Realização: ABCD-USP USP   Logos de Redes Sociais: Freepik

Buscando em bases de dados remotas. Favor aguardar.