Fast and Simple Algorithms for Recognizing Chordal Comparability Graphs and Interval Graphs
Fast and Simple Algorithms for Recognizing Chordal Comparability Graphs and Interval Graphs
复制标题
用于识别弦可比图和区间图的快速而简单的算法
DOI：
10.1137/s0097539792224814
复制
发表时间：
1999
期刊：
影响因子：
--
通讯作者：
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.