P4-TREES AND SUBSTITUTION DECOMPOSITION

被引：78
作者：
SPINRAD, J
机构：
[1] Department of Computer Science, Vanderbilt University, Nashville
来源：
DISCRETE APPLIED MATHEMATICS | 1992年 / 39卷 / 03期
基金：
美国国家科学基金会;
关键词：
D O I：
10.1016/0166-218X(92)90180-I
中图分类号：
O29 [应用数学];
学科分类号：
070104 ;
摘要：
This paper introduces a new data structure called a P4-tree, and uses the data structure as part of an algorithm to find the substitution decomposition of a graph in O(malpha(m,n)) time.
引用
收藏
页码：263 / 291
页数：29
相关论文
共 29 条
[1]   A FAST ALGORITHM FOR THE DECOMPOSITION OF GRAPHS AND POSETS [J].
BUER, H ;
MOHRING, RH .
MATHEMATICS OF OPERATIONS RESEARCH, 1983, 8 (02) :170-184
[2]   PARTITIVE HYPERGRAPHS [J].
CHEIN, M ;
HABIB, M ;
MAURER, MC .
DISCRETE MATHEMATICS, 1981, 37 (01) :35-50
[3]   ON TESTING ISOMORPHISM OF PERMUTATION GRAPHS [J].
COLBOURN, CJ .
NETWORKS, 1981, 11 (01) :13-21
[4]   COMPLEMENT REDUCIBLE GRAPHS [J].
CORNEIL, DG ;
LERCHS, H ;
BURLINGHAM, LS .
DISCRETE APPLIED MATHEMATICS, 1981, 3 (03) :163-174
[5]   A LINEAR RECOGNITION ALGORITHM FOR COGRAPHS [J].
CORNEIL, DG ;
PERL, Y ;
STEWART, LK .
SIAM JOURNAL ON COMPUTING, 1985, 14 (04) :926-934
[6]   DECOMPOSITION OF DIRECTED-GRAPHS [J].
CUNNINGHAM, WH .
SIAM JOURNAL ON ALGEBRAIC AND DISCRETE METHODS, 1982, 3 (02) :214-228
[7]  
GABOW HN, 1983, 15TH P ANN ACM S THE, P246
[8]   TRANSITIV ORIENTIERBARE GRAPHEN [J].
GALLAI, T .
ACTA MATHEMATICA ACADEMIAE SCIENTIARUM HUNGARICAE, 1967, 18 (1-2) :25-&
[9]  
GLUMBIC MC, 1977, J COMB THEORY B, V22, P68
[10]  
Golumbic M. C., 1980, ALGORITHMIC GRAPH TH
123