{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,19]],"date-time":"2025-09-19T07:26:13Z","timestamp":1758266773876},"reference-count":32,"publisher":"Elsevier BV","issue":"1-2","license":[{"start":{"date-parts":[[1994,9,1]],"date-time":"1994-09-01T00:00:00Z","timestamp":778377600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"},{"start":{"date-parts":[[2013,7,17]],"date-time":"2013-07-17T00:00:00Z","timestamp":1374019200000},"content-version":"vor","delay-in-days":6894,"URL":"https:\/\/www.elsevier.com\/open-access\/userlicense\/1.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Theoretical Computer Science"],"published-print":{"date-parts":[[1994,9]]},"DOI":"10.1016\/0304-3975(94)90233-x","type":"journal-article","created":{"date-parts":[[2002,7,26]],"date-time":"2002-07-26T03:47:37Z","timestamp":1027655257000},"page":"209-227","source":"Crossref","is-referenced-by-count":10,"title":["A k-structure generalization of the theory of 2-structures"],"prefix":"10.1016","volume":"132","author":[{"given":"A.","family":"Ehrenfeucht","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"R.","family":"McConnell","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"78","reference":[{"key":"10.1016\/0304-3975(94)90233-X_bib1","doi-asserted-by":"crossref","first-page":"19","DOI":"10.1002\/jgt.3190020104","article-title":"Graphs with unique maximal clumpings","volume":"2","author":"Blass","year":"1978","journal-title":"J. Graph Theory"},{"key":"10.1016\/0304-3975(94)90233-X_bib2","series-title":"Extremal Graph Theory","author":"Bollabas","year":"1978"},{"key":"10.1016\/0304-3975(94)90233-X_bib3","doi-asserted-by":"crossref","first-page":"151","DOI":"10.1016\/0304-3975(94)90231-3","article-title":"Primitive 2-structures with the (n\u22122) property","volume":"132","author":"Bonizzoni","year":"1994","journal-title":"Theoret. Comput. Sci."},{"key":"10.1016\/0304-3975(94)90233-X_bib4","doi-asserted-by":"crossref","first-page":"35","DOI":"10.1016\/0012-365X(81)90138-2","article-title":"Partitive hypergraphs","volume":"37","author":"Chein","year":"1981","journal-title":"Discrete Math."},{"key":"10.1016\/0304-3975(94)90233-X_bib5","series-title":"Tech. Report R.R. LIRMM no. 92-023","article-title":"An efficient algorithm to recognize prime undirected graphs","author":"Cournier","year":"1992"},{"key":"10.1016\/0304-3975(94)90233-X_bib6","doi-asserted-by":"crossref","first-page":"734","DOI":"10.4153\/CJM-1980-057-7","article-title":"A combinatorial decomposition theory","volume":"32","author":"Cunningham","year":"1980","journal-title":"Canadian J. Math."},{"key":"10.1016\/0304-3975(94)90233-X_bib7","doi-asserted-by":"crossref","first-page":"283","DOI":"10.1006\/jagm.1994.1013","article-title":"An O(n2) divide-and-conquer algorithm to compute the prime tree decomposition of two-structures and modular decomposition of graphs","volume":"16","author":"Ehrenfeucht","year":"1994","journal-title":"J. Algorithms"},{"key":"10.1016\/0304-3975(94)90233-X_bib8","author":"Ehrenfeucht","year":"1993","journal-title":"Invariants of 2-structures on groups of labels"},{"key":"10.1016\/0304-3975(94)90233-X_bib9","doi-asserted-by":"crossref","first-page":"277","DOI":"10.1016\/0304-3975(90)90129-6","article-title":"Theory of 2-structures","volume":"70","author":"Ehrenfeucht","year":"1990","journal-title":"Theoret. Comput. Sci."},{"key":"10.1016\/0304-3975(94)90233-X_bib10","doi-asserted-by":"crossref","first-page":"305","DOI":"10.1016\/0304-3975(90)90130-A","article-title":"Theory of 2-structures","volume":"70","author":"Ehrenfeucht","year":"1990","journal-title":"Theoret. Comput. Sci."},{"key":"10.1016\/0304-3975(94)90233-X_bib11","doi-asserted-by":"crossref","first-page":"343","DOI":"10.1016\/0304-3975(90)90131-Z","article-title":"Primitivity is hereditary for 2-structures","volume":"70","author":"Ehrenfeucht","year":"1990","journal-title":"Theoret. Comput. Sci."},{"key":"10.1016\/0304-3975(94)90233-X_bib12","doi-asserted-by":"crossref","first-page":"25","DOI":"10.1007\/BF02020961","article-title":"Transitiv orientierbare graphen","volume":"18","author":"Gallai","year":"1967","journal-title":"Acta Math. Acad. Sci. Hungar"},{"key":"10.1016\/0304-3975(94)90233-X_bib13","series-title":"Algorithmic Graph Theory and Perfect Graphs","author":"Golumbic","year":"1980"},{"key":"10.1016\/0304-3975(94)90233-X_bib14","doi-asserted-by":"crossref","first-page":"201","DOI":"10.1016\/0166-218X(79)90043-X","article-title":"On the X-join decomposition for undirected graphs","volume":"1","author":"Habib","year":"1979","journal-title":"Discrete Appl. Math."},{"key":"10.1016\/0304-3975(94)90233-X_bib15","author":"Harju","year":"1993","journal-title":"Decompositions of infinite 2-structures"},{"key":"10.1016\/0304-3975(94)90233-X_bib16","series-title":"Graphs and Orders","first-page":"3","article-title":"Comparability graphs","author":"Kelly","year":"1985"},{"key":"10.1016\/0304-3975(94)90233-X_bib17","unstructured":"R.M. McConnell, An O(n2) incremental algorithm to compute the modular decomposition of a 2-structure, Algorithmica, to appear."},{"key":"10.1016\/0304-3975(94)90233-X_bib18","first-page":"536","article-title":"Linear-time modular decomposition and efficient transitive orientation of comparability graphs","author":"McConnell","year":"1994","journal-title":"Proceedings of the Fifth Annual ACM-SIAM Symposium on Discrete Algorithms"},{"key":"10.1016\/0304-3975(94)90233-X_bib19","series-title":"Graphs and Orders","first-page":"41","article-title":"Algorithmic aspects of comparability graphs and interval graphs","author":"M\u00f6hring","year":"1985"},{"key":"10.1016\/0304-3975(94)90233-X_bib20","doi-asserted-by":"crossref","first-page":"195","DOI":"10.1007\/BF02022041","article-title":"Algorithmic aspects of the substitution decomposition optimization over relations, set systems and boolean functions","volume":"4","author":"M\u00f6hring","year":"1985","journal-title":"Ann. Oper. Res"},{"key":"10.1016\/0304-3975(94)90233-X_bib21","doi-asserted-by":"crossref","first-page":"63","DOI":"10.1016\/0012-365X(84)90035-9","article-title":"Almost all comparability graphs are UPO","volume":"50","author":"M\u00f6hring","year":"1984","journal-title":"Discrete Math."},{"key":"10.1016\/0304-3975(94)90233-X_bib22","first-page":"257","article-title":"Substitution decomposition and connections with combinatorial optimization","volume":"19","author":"M\u00f6hring","year":"1984","journal-title":"Ann. Discrete Math."},{"key":"10.1016\/0304-3975(94)90233-X_bib23","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/58562.59300","article-title":"Incremental modular decomposition","volume":"36","author":"Muller","year":"1989","journal-title":"J. ACM"},{"key":"10.1016\/0304-3975(94)90233-X_bib24","doi-asserted-by":"crossref","first-page":"191","DOI":"10.1016\/0012-365X(93)90516-V","article-title":"Critically indecomposable partially ordered sets, graphs, tournaments and other binary relational structures","volume":"113","author":"Schmerl","year":"1993","journal-title":"Discrete Math."},{"key":"10.1016\/0304-3975(94)90233-X_bib25","doi-asserted-by":"crossref","first-page":"497","DOI":"10.1007\/BF00967091","article-title":"Partially ordered sets and their comparability graphs","volume":"11","author":"Shevrin","year":"1970","journal-title":"Siberian Math. J."},{"key":"10.1016\/0304-3975(94)90233-X_bib26","doi-asserted-by":"crossref","first-page":"606","DOI":"10.1287\/opre.34.4.606","article-title":"Optimal sequencing by modular decomposition","volume":"34","author":"Sidney","year":"1986","journal-title":"Oper. Res."},{"key":"10.1016\/0304-3975(94)90233-X_bib27","doi-asserted-by":"crossref","first-page":"263","DOI":"10.1016\/0166-218X(92)90180-I","article-title":"P4 trees and substitution decomposition","volume":"39","author":"Spinrad","year":"1992","journal-title":"Discrete Appl. Math."},{"key":"10.1016\/0304-3975(94)90233-X_bib28","doi-asserted-by":"crossref","first-page":"658","DOI":"10.1137\/0214048","article-title":"On comparability and permutation graphs","volume":"14","author":"Spinrad","year":"1985","journal-title":"SIAM J. Comput."},{"key":"10.1016\/0304-3975(94)90233-X_bib29","series-title":"Proc. 10th Coll. on Automata, Languages, and Programming","first-page":"676","article-title":"Recognition and isomorphism of two-dimensional partial orders","volume":"Vol. 154","author":"Spinrad","year":"1983"},{"key":"10.1016\/0304-3975(94)90233-X_bib30","first-page":"113","article-title":"Zur Strukturtheorie endlicher nichtdeterministischer Automaten I","volume":"17","author":"Strassner","year":"1981","journal-title":"J. Inform. Process. Cybernetics (EIK)"},{"key":"10.1016\/0304-3975(94)90233-X_bib31","first-page":"511","article-title":"Zur Strukturtheorie endlicher nichtdeterministischer Automaten II","volume":"17","author":"Strassner","year":"1981","journal-title":"J. Inform. Process. Cybernetics (EIK)"},{"key":"10.1016\/0304-3975(94)90233-X_bib32","doi-asserted-by":"crossref","first-page":"299","DOI":"10.1137\/0211023","article-title":"The recognition of series-parallel digraphs","volume":"11","author":"Valdes","year":"1982","journal-title":"SIAM J. Comput."}],"container-title":["Theoretical Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:030439759490233X?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:030439759490233X?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2019,4,13]],"date-time":"2019-04-13T04:28:47Z","timestamp":1555129727000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/030439759490233X"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1994,9]]},"references-count":32,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[1994,9]]}},"alternative-id":["030439759490233X"],"URL":"https:\/\/doi.org\/10.1016\/0304-3975(94)90233-x","relation":{},"ISSN":["0304-3975"],"issn-type":[{"value":"0304-3975","type":"print"}],"subject":[],"published":{"date-parts":[[1994,9]]}}}