{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,14]],"date-time":"2026-10-14T01:28:22Z","timestamp":1791941302461,"version":"4.3.4"},"reference-count":13,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"4","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[1985,11]]},"abstract":"<jats:p>Cographs are the graphs formed from a single vertex under the closure of the operations of union and complement. Another characterization of cographs is that they are the undirected graphs with no induced paths on four vertices. Cographs arise naturally in such application areas as examination scheduling and automatic clustering of index terms. Furthermore, it is known that cographs have a unique tree representation called a cotree. Using the cotree it is possible to design very fast polynomial time algorithms for problems which are intractable for graphs in general. Such problems include chromatic number, clique determination, clustering, minimum weight domination, isomorphism, minimum fill-in and Hamiltonicity. In this paper we present a linear time algorithm for recognizing cographs and constructing their cotree representation.<\/jats:p>","DOI":"10.1137\/0214065","type":"journal-article","created":{"date-parts":[[2005,2,24]],"date-time":"2005-02-24T06:25:35Z","timestamp":1109226335000},"page":"926-934","source":"Crossref","is-referenced-by-count":470,"title":["A Linear Recognition Algorithm for Cographs"],"prefix":"10.1137","volume":"14","author":[{"given":"D. G.","family":"Corneil","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Y.","family":"Perl","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"L. K.","family":"Stewart","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2006,7,13]]},"reference":[{"key":"R1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(76)80045-1"},{"key":"R2","doi-asserted-by":"crossref","unstructured":"S. A. Cook,  The complexity of theorem-proving procedures,  Proc. 3rd Annual ACM Symposium on Theory of Computing, ACM, New York,  1971,  151\u2013158","DOI":"10.1145\/800157.805047"},{"key":"R3","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(81)90013-5"},{"key":"R4","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(84)90088-X"},{"key":"R5","first-page":"249","volume":"43","author":"Corneil D. G.","year":"1984","journal-title":"Congr. Numer."},{"key":"R6","volume-title":"Computers and intractability","author":"Garey Michael R.","year":"1979"},{"key":"R7","doi-asserted-by":"publisher","DOI":"10.1145\/321479.321480"},{"key":"R8","doi-asserted-by":"publisher","DOI":"10.1145\/321850.321852"},{"key":"R9","doi-asserted-by":"publisher","DOI":"10.1002\/net.1975.5.1.45"},{"key":"R10","doi-asserted-by":"publisher","DOI":"10.1137\/0205021"},{"key":"R11","doi-asserted-by":"crossref","unstructured":"J. Spinrad,  Transitive orientation in  O(n2) time,  Proc. 15th Annual ACM Symposium on Theory of Computing, ACM, New York,  1983,  457\u2013466","DOI":"10.1145\/800061.808777"},{"key":"R12","unstructured":"L. Stewart,  Cographs, a class of tree representable graphs, TR 126\/78, Dept. Computer Science, Univ. Toronto, Toronto, Ontario,  1978"},{"key":"R13","doi-asserted-by":"publisher","DOI":"10.1137\/0211023"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/0214065","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:40:01Z","timestamp":1787337601000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/0214065"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1985,11]]},"references-count":13,"journal-issue":{"issue":"4","published-print":{"date-parts":[[1985,11]]}},"alternative-id":["10.1137\/0214065"],"URL":"https:\/\/doi.org\/10.1137\/0214065","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[1985,11]]}}}