An Incremental Linear-Time Algorithm for Recognizing Interval Graphs
An Incremental Linear-Time Algorithm for Recognizing Interval Graphs
复制标题
一种识别区间图的增量线性时间算法
DOI：
10.1137/0218005
复制
发表时间：
1989
期刊：
影响因子：
--
通讯作者：
R. Möhring
中科院分区：
文献类型：
--
作者：
Norbert Korte;R. Möhring
已知的识别区间图的最快算法[S.Booth和S.Lucker，J.系统科学，13(1976)，pp.335-379]以相当复杂的方式迭代地操纵给定图的所有极大团的系统，以便构造连续排列(更准确地，所有可能的连续排列的树表示)。本文给出了一个简单得多的算法，它使用了区间图的一种相关的、但信息量更大的树表示法。通过以预定义的顺序将顶点添加到图中以增量方式构建该树，使得添加顶点u花费$O(|{\操作员名称{adj}}(U)|+1)$摊销时间。
The fastest-known algorithm for recognizing interval graphs [S. Booth and S. Lucker, J. Comput. System Sci., 13 (1976), pp. 335–379] iteratively manipulates the system of all maximal cliques of the given graph in a rather complicated way in order to construct a consecutive arrangement (more precisely, a tree representation of all possible consecutive arrangements). This paper presents a much simpler algorithm using a related, but much more informative tree representation of interval graphs. This tree is constructed in an incremental fashion by adding vertices to the graph in a predefined order such that adding a vertex u takes $O(|{\operatorname{Adj}}(u)| + 1)$ amortized time.