An O(n²) Algorithm for Undirected Split Decompositon

An O(n²) Algorithm for Undirected Split Decompositon
复制标题

一种 O(n²) 无向分裂分解算法

DOI：
--
复制
发表时间：
1994
期刊：
J. Algorithms
影响因子：
--
通讯作者：
J. Spinrad
J. Spinrad
中科院分区：
--
文献类型：
--
作者：
T. Ma;J. Spinrad

文献摘要

被引文献

相似文献

图的无向分裂或连接分解的时间复杂度从Ω（n3）降低到O（n2）。在一个配套文件中，这一结果被用来提高识别圆图的时间界限。
The time complexity of the undirected split, or join, decomposition of a graph is reduced from Ω(n3) to O(n2). In a companion paper, this result is used to improve the time bound for recognizing circle graphs.