A Faster Parameterized Algorithm for Treedepth
A Faster Parameterized Algorithm for Treedepth
复制标题
一种更快的树深度参数化算法
DOI：
10.1007/978-3-662-43948-7_77
复制
发表时间：
2014
期刊：
影响因子：
--
通讯作者：
Somnath Sikdar
中科院分区：
文献类型：
--
作者：
Felix Reidl;Peter Rossmanith;Fernando Sánchez Villaamil;Somnath Sikdar
宽度测量树深度，也称为顶点排序、居中着色和消除树高度，是一个成熟的概念，最近又重新引起了人们的兴趣。我们提出了一种算法——给定一个 nn 顶点图、一个宽度 w 的树分解和一个整数——决定输入图的树深度最多是否为 2O(wt)·n。我们用它来构建不需要树分解作为其输入的一部分的进一步算法：一个简单的算法，它在线性时间内决定固定点的树深度，从而回答 Ossona de Mendez 和 Nešetřil 提出的关于是否存在这样的算法的开放性问题，一个运行时间的快速算法和一个运行时间为 2O(tlogt)·n 的弦图算法。
The width measuretreedepth, 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 ann-vertex graph, a tree decomposition of widthw, and an integert—decides whether the input graph has treedepth at mosttin time 2O(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 fixedt, 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 timeand an algorithm for chordal graphs with running time 2O(tlogt)·n.
登录
查看更多内容
线性时间内树的最优节点排序
影响因子：
0.5
作者：
A. Schäffer
通讯作者：
A. Schäffer
影响因子：
1
作者：
COURCELLE, B
通讯作者：
COURCELLE, B
影响因子：
1.5
作者：
K. Kaya;B. Uçar
通讯作者：
B. Uçar
树宽的 O(c^k n) 5 近似算法
DOI：
--
发表时间：
2013
期刊：
影响因子：
--
作者：
H. Bodlaender;Markus S. Dregi;F. Fomin;D. Lokshtanov
通讯作者：
D. Lokshtanov
关于排列和其他图的顶点排序
DOI：
10.1007/3-540-57785-8_187
发表时间：
1994
期刊：
Discret. Appl. Math.
影响因子：
--
作者：
J. Deogun;T. Kloks;D. Kratsch;H. Müller
通讯作者：
H. Müller