{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,22]],"date-time":"2026-08-22T08:47:20Z","timestamp":1787388440964,"version":"build-2736575974"},"reference-count":14,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"3","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[1985,8]]},"abstract":"<jats:p>This paper presents a technique for orienting a comparability graph transitively in $O(n^2 )$ time. The best previous algorithm for this problem required $\\Omega (n^3 )$ time. When combined with a result in [SP], we can recognize permutation graphs in $O(n^2 )$ time, and determine in the same time complexity whether two permutation graphs are isomorphic. The orientation algorithm can also be used to reduce the problem of recognizing comparability graphs to that of recognizing transitive graphs. This gives an upper bound of $O(n^{2.49 + } )$ for comparability graph recognition, while the fastest previous algorithms required $\\Omega (n^3 )$ time.<\/jats:p>","DOI":"10.1137\/0214048","type":"journal-article","created":{"date-parts":[[2005,2,24]],"date-time":"2005-02-24T06:25:35Z","timestamp":1109226335000},"page":"658-670","source":"Crossref","is-referenced-by-count":122,"title":["On Comparability and Permutation Graphs"],"prefix":"10.1137","volume":"14","author":[{"given":"Jeremy","family":"Spinrad","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2006,8,2]]},"reference":[{"key":"R1","volume-title":"The design and analysis of computer algorithms","author":"Aho A.","year":"1975"},{"key":"R2","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230110103"},{"key":"R3","doi-asserted-by":"publisher","DOI":"10.1137\/0211038"},{"key":"R4","doi-asserted-by":"publisher","DOI":"10.2307\/2371374"},{"key":"R5","doi-asserted-by":"publisher","DOI":"10.4153\/CJM-1964-055-5"},{"key":"R6","doi-asserted-by":"publisher","DOI":"10.1007\/BF02253207"},{"key":"R7","volume-title":"Algorithmic graph theory and perfect graphs","author":"Golumbic M.","year":"1980"},{"key":"R8","first-page":"1370","volume":"254","author":"Ghouila-Houri Alain","year":"1962","journal-title":"C. R. Acad. Sci. Paris"},{"key":"R9","unstructured":"J. Muller, J. Spinrad,  On-line modular decomposition, Tech. Rep., GIT-ICS-84\/11, Georgia Institute of Technology"},{"key":"R10","doi-asserted-by":"publisher","DOI":"10.4153\/CJM-1971-016-5"},{"key":"R11","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230120407"},{"key":"R12","unstructured":"J. Spinrad, Ph.D. Thesis,  Two dimensional partial orders, Princeton Univ., Princeton, NJ,  1982 0521.68081"},{"key":"R13","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0036947"},{"key":"R14","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\/0214048","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:39:13Z","timestamp":1787337553000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/0214048"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1985,8]]},"references-count":14,"journal-issue":{"issue":"3","published-print":{"date-parts":[[1985,8]]}},"alternative-id":["10.1137\/0214048"],"URL":"https:\/\/doi.org\/10.1137\/0214048","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[1985,8]]}}}