Bounded degree graph inference from walks
Bounded degree graph inference from walks
复制标题
从步行中进行有界度图推断
DOI：
10.1016/s0022-0000(05)80089-3
复制
发表时间：
1991
期刊：
影响因子：
--
通讯作者：
V. Raghavan
中科院分区：
文献类型：
--
作者：
V. Raghavan
Aslam和Rivest考虑了一个问题，即推断度boundk与图的行走中看到的颜色序列一致的最小边着色图。利用某些重写规则集的Church-Rosser性质，他们给出了k = 2情况下的多项式时间算法。他们的想法的直接实现导致O（n5）算法，其中是步行的长度。在本文中，我们进一步发展了他们的思想，并给出了一个O（nlogn）算法相同的问题。我们还证明了，如果度boundkis大于2，那么决策版本的问题是NP-完全的，从而解决了Aslam和Rivest的猜想。
Aslam and Rivest considered the problem of inferring the smallest edge-colored graph of degree boundkconsistent with the sequence of colors seen in a walk of the graph. Using Church-Rosser properties of certain sets of rewrite rules, they gave a polynomial time algorithm for the case ofk= 2. The straightforward implementation of their ideas results in anO(n5) algorithm, wherenis the length of the walk. In this paper, we develop their ideas further and give anO(nlogn) algorithm for the same problem. We also show that if the degree boundkis greater than two, then the decision version of the problem is NP-complete, thus settling a conjecture of Aslam and Rivest.