Primo Search

# 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

• 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