Incremental modular decomposition

Journal of the ACM - Tập 36 Số 1 - Trang 1-19 - 1989
John H. Muller1, Jeremy Spinrad2
1Univ. of Toronto, Toronto, Ont., Canada
2Vanderbilt Univ., Nashville, TN

Tóm tắt

Modular decomposition is a form of graph decomposition that has been discovered independently by researchers in graph theory, game theory, network theory, and other areas. This paper reduces the time needed to find the modular decomposition of a graph from Ω( n 3 ) to Ο( n 2 ). Together with a new algorithm for transitive orientation given in [21], this leads to fast new algorithms for a number of problems in graph recognition and isomorphism, including recognition of comparability graphs and permutation graphs. The new algorithm works by inserting each vertex successively into the decomposition tree, using Ο( n ) time to insert each vertex.

Từ khóa


Tài liệu tham khảo

BLASS A, 1978, Graphs with unique maximal clumpings, J. Graph Theory, 2, 19, 10.1002/jgt.3190020104

BUER H., 1983, A fast algorithm for the decomposition of graphs and posets, Math. Oper. Res., 3, 170, 10.1287/moor.8.2.170

COLBOURN C.J, On testing isomorphism of permutation graphs, Networks, 11, 13, 10.1002/net.3230110103

CORNEIL D. G., 1985, A linear recognition algorithm for cographs, SIAM J. Comput., 14, 926, 10.1137/0214065

CUNNXNGHAM W. Decomposition of directed graphs. SIAM ~ Algorithms and Discrete Meth. 3 (1982) 214-228. CUNNXNGHAM W. Decomposition of directed graphs. SIAM ~ Algorithms and Discrete Meth. 3 (1982) 214-228.

GALLAI T, 1967, Transitiv orientierbare graphen, Acta Math. Acad. Sci. Hung., 18, 25, 10.1007/BF02020961

GOLUMBIC M., 1977, Fla., 199

GOLUMBIC M., 1980, Fla.

HABIB M., 1979, On the X-join decomposition for undirected graphs, Discrete Appl. Discrete Math., 1, 201, 10.1016/0166-218X(79)90043-X

H!RAGUSHL T. On the dimension of partially ordered seLs. Sci. Rep. Kanazawa Univ. ! (195 l) 77-94. H!RAGUSHL T. On the dimension of partially ordered seLs. Sci. Rep. Kanazawa Univ. ! (195 l) 77-94.

HOLLENBACH B., 1983, Ga.

MOHRSNG R.H., 1985, Ed. Reidel, 41

MOHRING R. H., 1984, Substitution decomposition and connections with{ combinatorial optimization, Ann. Discrete Math., 19, 257

MONMA C. L., 1984, Bellcore

SABIDUSS, 1961, Graph derivatives, Math. Z., 76, 385, 10.1007/BF01210984

SHEVRIN L. AND FILIPPOV N. Partially ordered sets and their comparability graphs. Sib. J. Math. ii (i970) 648-607 {English translation). SHEVRIN L. AND FILIPPOV N. Partially ordered sets and their comparability graphs. Sib. J. Math. ii (i970) 648-607 {English translation).

SHAPLEY L., 1967, Eds. Springer-Verlag, 246

SIDNEY D., 1985, Ont.

SIELKEN R., 1979, Decision Information c. Tsokos and r.thrall eds, 153

SPINRAD J. Two dimensional partial orders. Ph.D. dissertation. Princeton Univ. Princeton N.J. 1982. SPINRAD J. Two dimensional partial orders. Ph.D. dissertation. Princeton Univ. Princeton N.J. 1982.

SP!NRAD~ J. On comparabi!ity and r~_rmutation oraphs. STAM.L Computo !4 (! 985) 658-670. SP!NRAD~ J. On comparabi!ity and r~_rmutation oraphs. STAM.L Computo !4 (! 985) 658-670.

SPINRAD J., 1983, Proceedings of the l Oth Colloquium on Automata, Languages and Programming, 676, 10.1007/BFb0036947

STERNER G., 1982, Ont.

Thông tin
Thông tin xuất bản

Journal of the ACM

Tập 36 Số 1

1-19

Thông tin tác giả