Portal de Periódicos da CAPES

A Faster Parameterized Algorithm for Treedepth

2014; Springer Science+Business Media; Linguagem: Inglês

10.1007/978-3-662-43948-7_77

1611-3349

Felix Reidl, Peter Rossmanith, Fernando Sánchez Villaamil, Somnath Sikdar,

Limits and Structures in Graph Theory

The width measure treedepth, also known as vertex ranking, centered coloring and elimination tree height, is a well-established notion which has recently seen a resurgence of interest. We present an algorithm which—given as input an n-vertex graph, a tree decomposition of width w, and an integer t—decides whether the input graph has treedepth at most t in time 2 O(wt) ·n. We use this to construct further algorithms which do not require a tree decomposition as part of their input: A simple algorithm which decides treedepth in linear time for a fixed t, thus answering an open question posed by Ossona de Mendez and Nešetřil as to whether such an algorithm exists, a fast algorithm with running time $2^{O(t^2)} \cdot n$ and an algorithm for chordal graphs with running time 2 O(t logt)·n.