A Simple Linear Time Split Decomposition Algorithm of Undirected Graphs

A Simple Linear Time Split Decomposition Algorithm of Undirected Graphs
复制标题

一种简单的无向图线性时间分割分解算法

DOI：
--
复制
发表时间：
2009
期刊：
arXiv.org
影响因子：
--
通讯作者：
M. Raffinot
M. Raffinot
中科院分区：
--
文献类型：
--
作者：
Pierre Charbit;F. D. Montgolfier;M. Raffinot

文献摘要

被引文献

相似文献

我们重新设计一个线性时间算法的无向图分裂分解的问题。虽然这个问题已经在[E. Dahlhaus，FSTTCS，1994]和[E. Dahlhaus，Journal of Algorithms 36（2）：205-240，2000]，我们提出了一个新的有充分根据的分裂分解理论背景，使我们能够清楚地设计和证明第一个简单的线性时间分裂分解算法。
We revisit the problem of designing a linear time algorithm for undirected graph split decomposition. Although that this problem has already been claimed to be solved in [E. Dahlhaus, FSTTCS, 1994] and [E. Dahlhaus, Journal of Algorithms 36(2):205-240, 2000], we present a new well founded theoretical background for split decomposition that allow us to clearly design and proove the rst simple linear time split decomposition algorithm.