THE SERIAL TRANSITIVE CLOSURE PROBLEM FOR TREES

作     者：BONET, ML BUSS, SR 

作者机构：UNIV CALIF SAN DIEGO DEPT MATH LA JOLLA CA 92093 USA 

出 版 物：《SIAM JOURNAL ON COMPUTING》 (工业与应用数学会计算杂志)

年 卷 期：1995年第24卷第1期

页      面：109-122页

核心收录：

学科分类：07[理学] 070104[理学-应用数学] 0701[理学-数学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

主　　题：TRANSITIVE CLOSURE GRAPH ALGORITHM INVERSE ACKERMANN FUNCTION WEAK SUPERCONCENTRATORS 

摘      要：The serial transitive closure problem is the problem, given a directed graph G and a list of edges, called closure edges, which are in the transitive closure of the graph, to generate all the closure edges from edges in G. A nearly linear upper bound is given on the number of steps in optimal solutions to the serial transitive closure problem for the case of graphs that are trees. Nearly linear means O(***(n)), where alpha is the inverse Ackermann function. This upper bound is optimal to within a constant factor.