{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,28]],"date-time":"2025-09-28T12:44:51Z","timestamp":1759063491969},"reference-count":32,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[1995,9,1]],"date-time":"1995-09-01T00:00:00Z","timestamp":809913600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[1995,9]]},"DOI":"10.1007\/bf01206330","type":"journal-article","created":{"date-parts":[[2005,2,25]],"date-time":"2005-02-25T08:24:38Z","timestamp":1109319878000},"page":"229-248","source":"Crossref","is-referenced-by-count":11,"title":["AnO(n 2) incremental algorithm for modular decomposition of graphs and 2-structures"],"prefix":"10.1007","volume":"14","author":[{"given":"R. M.","family":"McConnell","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"CR1","doi-asserted-by":"crossref","first-page":"277","DOI":"10.1016\/0304-3975(90)90129-6","volume":"70","author":"A. Ehrenfeucht","year":"1990","unstructured":"A. Ehrenfeucht and G. Rozenberg, Theory of 2-structures, part 1: Clans, basic subclasses, and morphisms,Theoretical Computer Science,70 (1990), 277?303.","journal-title":"Theoretical Computer Science"},{"key":"CR2","doi-asserted-by":"crossref","first-page":"305","DOI":"10.1016\/0304-3975(90)90130-A","volume":"70","author":"A. Ehrenfeucht","year":"1990","unstructured":"A. Ehrenfeucht and G. Rosenberg, Theory of 2-structures, part 2: Representations through labeled tree families,Theoretical Computer Science,70 (1990), 305?342.","journal-title":"Theoretical Computer Science"},{"key":"CR3","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/58562.59300","volume":"36","author":"J. H. Muller","year":"1989","unstructured":"J. H. Muller and J. Spinrad, Incremental modular decomposition,Journal of the Association for Computing Machinery,36 (1989), 1?19.","journal-title":"Journal of the Association for Computing Machinery"},{"key":"CR4","first-page":"257","volume":"19","author":"R. H. M\u00f6hring","year":"1984","unstructured":"R. H. M\u00f6hring and F. J. Radermacher, Substitution decomposition for discrete structures and connections with combinatorial optimization,Annals of Discrete Mathematics,19 (1984), 257?356.","journal-title":"Annals of Discrete Mathematics"},{"key":"CR5","doi-asserted-by":"crossref","first-page":"195","DOI":"10.1007\/BF02022041","volume":"4","author":"R. H. M\u00f6hring","year":"1985\/6","unstructured":"R. H. M\u00f6hring, Algorithmic aspects of the substitution decomposition in optimization over relations, set systems and boolean functions,Annals of Operation Research,4 (1985\/6), 195?225.","journal-title":"Annals of Operation Research"},{"key":"CR6","doi-asserted-by":"crossref","first-page":"41","DOI":"10.1007\/978-94-009-5315-4_2","volume-title":"Graphs and Orders","author":"R. H. M\u00f6hring","year":"1985","unstructured":"R. H. M\u00f6hring, Algorithmic aspects of comparability graphs and interval graphs, inGraphs and Orders (I. Rival, editor), Reidel, Boston, 1985, pp. 41?101."},{"key":"CR7","first-page":"629","volume":"266","author":"J. H. Schmerl","year":"1981","unstructured":"J. H. Schmerl, Arborescent structures, II: interpretability in the theory of trees,Transactions of the American Mathematical Society,266 (1981), 629?643.","journal-title":"Transactions of the American Mathematical Society"},{"key":"CR8","doi-asserted-by":"crossref","first-page":"25","DOI":"10.1007\/BF02020961","volume":"18","author":"T. Gallai","year":"1967","unstructured":"T. Gallai, Transitiv orientierbare graphen,Acta Mathematica Acadamiae Scientiarum Hungaricae,18 (1967), 25?66.","journal-title":"Acta Mathematica Acadamiae Scientiarum Hungaricae"},{"key":"CR9","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1007\/978-94-009-5315-4_1","volume-title":"Graphs and Order","author":"D. Kelly","year":"1985","unstructured":"D. Kelly, Comparability graphs, inGraphs and Order (I. Rival, editor), Reidel, Boston, 1985, pp. 3?40."},{"key":"CR10","doi-asserted-by":"crossref","first-page":"201","DOI":"10.1016\/0166-218X(79)90043-X","volume":"1","author":"M. Habib","year":"1979","unstructured":"M. Habib and M. C. Maurer, On the X-join decomposition for undirected graphs,Discrete Applied Mathematics,1 (1979), 201?207.","journal-title":"Discrete Applied Mathematics"},{"key":"CR11","volume-title":"Algorithmic Graph Theory and Perfect Graphs","author":"M. C. Golumbic","year":"1980","unstructured":"M. C. Golumbic,Algorithmic Graph Theory and Perfect Graphs, Academic Press, New York, 1980."},{"key":"CR12","doi-asserted-by":"crossref","first-page":"19","DOI":"10.1002\/jgt.3190020104","volume":"2","author":"A. Blass","year":"1978","unstructured":"A. Blass, Graphs with unique maximal dumpings,Journal of Graph Theory,2 (1978), 19?24.","journal-title":"Journal of Graph Theory"},{"key":"CR13","doi-asserted-by":"crossref","first-page":"497","DOI":"10.1007\/BF00967091","volume":"11","author":"L. N. Shevrin","year":"1970","unstructured":"L. N. Shevrin and N. D. Filippov, Partially ordered sets and their comparability graphs,Siberian Mathematical Journal,11 (1970), 497?509.","journal-title":"Siberian Mathematical Journal"},{"key":"CR14","first-page":"926","volume":"3","author":"D. G. Corneil","year":"1985","unstructured":"D. G. Corneil, Y. Perl, and L. K. Stewart, A linear recognition algorithm for cographs,SIAM Journal on Algebraic and Discrete Methods,3 (1985), 926?934.","journal-title":"SIAM Journal on Algebraic and Discrete Methods"},{"key":"CR15","doi-asserted-by":"crossref","first-page":"299","DOI":"10.1137\/0211023","volume":"11","author":"J. Valdes","year":"1982","unstructured":"J. Valdes, R. E. Tarjan, and E. L. Lawler, The recognition of series-parallel digraphs,SIAM Journal on Computing,11 (1982), 299?313.","journal-title":"SIAM Journal on Computing"},{"key":"CR16","doi-asserted-by":"crossref","first-page":"209","DOI":"10.1016\/0304-3975(94)90233-X","volume":"132","author":"A. Ehrenfeucht","year":"1994","unstructured":"A. Ehrenfeucht and R. M. McConnell, Ak-structure generalization of the theory of 2-structures,Theoretical Computer Science,132 (1994), 209?227.","journal-title":"Theoretical Computer Science"},{"key":"CR17","doi-asserted-by":"crossref","first-page":"734","DOI":"10.4153\/CJM-1980-057-7","volume":"32","author":"W. H. Cunningham","year":"1980","unstructured":"W. H. Cunningham and J. Edmonds, A combinatorial decomposition theory,Canadian Journal of Mathematics,32 (1980), 734?765.","journal-title":"Canadian Journal of Mathematics"},{"key":"CR18","doi-asserted-by":"crossref","first-page":"303","DOI":"10.1016\/0012-365X(90)90067-R","volume":"81","author":"D. Wagner","year":"1990","unstructured":"D. Wagner, Decomposition of k-ary relations,Discrete Mathematics,81 (1990), 303?322.","journal-title":"Discrete Mathematics"},{"key":"CR19","first-page":"281","volume-title":"Proceedings of the 3rd South-Eastern Conference on Combinatorics, Graph Theory and Computing","author":"L. O. James","year":"1972","unstructured":"L. O. James, R. G. Stanton, and D. D. Cowan, Graph decomposition for undirected graphs, inProceedings of the 3rd South-Eastern Conference on Combinatorics, Graph Theory and Computing (F. Hoffman and R. B. Levow, editors), Utilitas Mathematica, Winnipeg, 1972, pp. 281?290."},{"key":"CR20","doi-asserted-by":"crossref","first-page":"170","DOI":"10.1287\/moor.8.2.170","volume":"8","author":"B. Buer","year":"1983","unstructured":"B. Buer and R. H. M\u00f6hring, A fast algorithm for the decomposition of graphs and posets,Mathematics of Operations Research,8 (1983), 170?184.","journal-title":"Mathematics of Operations Research"},{"key":"CR21","doi-asserted-by":"crossref","first-page":"68","DOI":"10.1016\/0095-8956(77)90049-1","volume":"22","author":"M. C. Golumbic","year":"1977","unstructured":"M. C. Golumbic, Comparability graphs and a new matroid,Journal of Combinatorial Theory, Series B,22 (1977), 68?90.","journal-title":"Journal of Combinatorial Theory, Series B"},{"key":"CR22","doi-asserted-by":"crossref","first-page":"214","DOI":"10.1137\/0603021","volume":"3","author":"W. H. Cunningham","year":"1982","unstructured":"W. H. Cunningham, Decomposition of directed graphs,SIAM Journal of Algebraic and Discrete Methods,3 (1982), 214?228.","journal-title":"SIAM Journal of Algebraic and Discrete Methods"},{"key":"CR23","volume-title":"Ph.D. thesis","author":"G. Steiner","year":"1982","unstructured":"G. Steiner, Machine Scheduling with Precedence Constraints, Ph.D. thesis, University of Waterloo, Waterloo, Ontario, 1982."},{"key":"CR24","volume-title":"Ph.D. thesis","author":"C. L. McCreary","year":"1987","unstructured":"C. L. McCreary, An Algorithm for Parsing a Graph Grammar, Ph.D. thesis, University of Colorado, Boulder, Co, 1987."},{"key":"CR25","unstructured":"A. Cournier and M. Habib, An Efficient Algorithm To Recognize Prime Undirected Graphs, Technical Report R.R. LIRMM 92-023, Laboratoire D'Informatique, de Robotique et de Microelectronique de Montpellier, 1992."},{"key":"CR26","doi-asserted-by":"crossref","first-page":"263","DOI":"10.1016\/0166-218X(92)90180-I","volume":"39","author":"J. P. Spinrad","year":"1992","unstructured":"J. P. Spinrad,P 4 trees and substitution decomposition,Discrete Applied Mathematics,39 (1992), 263?291.","journal-title":"Discrete Applied Mathematics"},{"key":"CR27","unstructured":"R. M. McConnell and J. P. Spinrad, Linear-time modular decomposition of undirected graphs and efficient transitive orientation of comparability graphs,Proceedings of the Symposium on Discrete Algorithms, 1993, pp. 536?545."},{"key":"CR28","unstructured":"M. C. Maurer, Joints et decompositions premi\u00e9res dans les graphes, Th\u00e8se 3\u00e8me cycle, Universit\u00e9 de Paris VI, 1977."},{"key":"CR29","doi-asserted-by":"crossref","first-page":"113","DOI":"10.1016\/0012-365X(94)90107-4","volume":"128","author":"A. Ehrenfeucht","year":"1994","unstructured":"A. Ehrenfeucht, T. Harju, and G. Rozenberg, Incremental construction of 2-structures,Discrete Mathematics,128 (1994), 113?141.","journal-title":"Discrete Mathematics"},{"key":"CR30","doi-asserted-by":"crossref","first-page":"283","DOI":"10.1006\/jagm.1994.1013","volume":"16","author":"A. Ehrenfeucht","year":"1994","unstructured":"A. Ehrenfeucht, H. N. Gabow, R. M. McCeonnell, and S. J. Sullivan, AnO(n 2) algorithm to compute the prime tree family of a 2-structure,Journal of Algorithms,16 (1994), 283?294.","journal-title":"Journal of Algorithms"},{"key":"CR31","doi-asserted-by":"crossref","first-page":"35","DOI":"10.1016\/0012-365X(81)90138-2","volume":"37","author":"M. Chein","year":"1981","unstructured":"M. Chein, M. Habib, and M. C. Maurer, Partitive hypergraphs,Discrete Mathematics,37 (1981), 35?50.","journal-title":"Discrete Mathematics"},{"key":"CR32","doi-asserted-by":"crossref","first-page":"191","DOI":"10.1016\/0012-365X(93)90516-V","volume":"113","author":"J. H. Schmerl","year":"1993","unstructured":"J. H. Schmerl and W. T. Trotter, Critically indecomposable partially ordered sets, graphs, tournaments and other binary relational structures,Discrete Mathematics,113 (1993), 191?205.","journal-title":"Discrete Mathematics"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01206330.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF01206330\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01206330","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,1]],"date-time":"2019-05-01T13:10:11Z","timestamp":1556716211000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF01206330"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1995,9]]},"references-count":32,"journal-issue":{"issue":"3","published-print":{"date-parts":[[1995,9]]}},"alternative-id":["BF01206330"],"URL":"https:\/\/doi.org\/10.1007\/bf01206330","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[1995,9]]}}}