skip to main content

Computing Tree-Depth Faster Than $$2^{n}$$ 2 n

Fomin, Fedor ; Giannopoulou, Archontia ; Pilipczuk, Michał

Algorithmica, 2015, Vol.73(1), pp.202-216 [Periódico revisado por pares]

Texto completo disponível

Citações Citado por
  • Título:
    Computing Tree-Depth Faster Than $$2^{n}$$ 2 n
  • Autor: Fomin, Fedor ; Giannopoulou, Archontia ; Pilipczuk, Michał
  • Assuntos: Exact algorithms ; Tree-depth ; Barrier
  • É parte de: Algorithmica, 2015, Vol.73(1), pp.202-216
  • Descrição: A connected graph has tree-depth at most k if it is a subgraph of the closure of a rooted tree whose height is at most k . We give an algorithm which for a given n -vertex graph G , in time \mathcal {O}^*}(1.9602^n) O ∗ ( 1 . 9602 n ) computes the tree-depth of G . Our algorithm is based on combinatorial results revealing the structure of minimal rooted trees whose closures contain G .
  • Idioma: Inglês

Buscando em bases de dados remotas. Favor aguardar.