Substitution Decomposition on Chordal Graphs and Applications
Substitution Decomposition on Chordal Graphs and Applications
复制标题
DOI：
10.1007/3-540-54945-5_49
复制
发表时间：
1991-12
期刊：
影响因子：
--
通讯作者：
W. Hsu;T. Ma
中科院分区：
文献类型：
--
作者：
W. Hsu;T. Ma
本文给出了弦图上置换分解的一个线性时间算法。在此基础上，我们提出了弦相似图传递定向的线性时间算法。该算法将弦相似性识别的复杂度从O（n ~ 2）降低到O（n+m）。我们还设计了一个简单的线性时间算法的区间图识别不涉及复杂的数据结构。
In this paper, we present a linear time algorithm for substitution decomposition on chordal graphs. Based on this result, we develop a linear time algorithm for transitive orientation on chordal comparability graphs. Which reduces the complexity of chordal comparability recognition from O(n2) to O(n+m). We also devise a simple linear time algorithm for interval graph recognition where no complicated data structure is involved.