A Linear Time Algorithm for Deciding Interval Graph Isomorphism
A Linear Time Algorithm for Deciding Interval Graph Isomorphism
复制标题
判定区间图同构的线性时间算法
DOI：
10.1145/322123.322125
复制
发表时间：
1979
期刊：
影响因子：
--
通讯作者：
K. Booth
中科院分区：
文献类型：
--
作者：
G. S. Lueker;K. Booth
作者：乔治·S·卢克 (Lueker, George S.)；布斯，凯洛格·S。摘要：一个图是区间图，当且仅当它的每个顶点都可以与实线上的一个区间相关联，并且当对应的区间具有非空交集时，两个顶点在图中恰好相邻。测试区间图同构的有效算法是使用称为 PQ 树的数据结构实现的。对于具有 n 个顶点和 e 个边的图，该算法以 0(n + e) 步运行。结果表明，对于更大的一类图，即弦图，同构与一般图一样困难。
Author(s): Lueker, George S.; Booth, Kellogg S. | Abstract: A graph is an interval graph if and only if each of its vertices can be associated with an interval on the real line in such a way that two vertices are adjacent in the graph exactly when the corresponding intervals have a nonempty intersection. An efficient algorithm for testing isomorphism of interval graphs is implemented using a data structure called a PQ-tree. The algorithm runs in 0(n + e) steps for graphs having n vertices and e edges. It is shown that for a somewhat larger class of graphs, namely the chordal graphs, isomorphism is as hard as for general graphs.