CHARACTERIZATION AND RECOGNITION OF PARTIAL 3-TREES
CHARACTERIZATION AND RECOGNITION OF PARTIAL 3-TREES
复制标题
DOI：
10.1137/0607033
复制
发表时间：
1986-04-01
期刊：
影响因子：
--
通讯作者：
PROSKUROWSKI, A
中科院分区：
文献类型：
--
作者：
ARNBORG, S;PROSKUROWSKI, A
我们对k-树类及其部分图和子图的兴趣是由一些实际问题引起的，这些问题涉及在受限线路和站点故障情况下通信网络的可靠性，以及数据库系统中查询的复杂性。我们发现了一组合流图约简，使得任何图都可以约简为空图，当且仅当它是3-tree的子图。这组约简产生了一个多项式时间算法，用于确定给定的图是否是部分3树，以及在3树中找到它的一个嵌入，当这种嵌入存在时。我们的结果推广了先前已知的部分2树（序列并行图）识别算法。
Our interest in the class ofk-trees and their partial graphs and subgraphs is motivated by some practical questions about the reliability of communication networks in the presence of constrained line- and site-failures, and about the complexity of queries in a data base system. We have found a set of confluent graph reductions such that any graph can be reduced to the empty graph if and only if it is a subgraph of a 3-tree. This set of reductions yields a polynomial time algorithm for deciding if a given graph is a partial 3-tree and for finding one of its embeddings in a 3-tree when such an embedding exists. Our result generalizes a previously known recognition algorithm for partial 2-trees (series-parallel graphs).