{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,22]],"date-time":"2025-03-22T04:17:53Z","timestamp":1742617073779,"version":"3.40.2"},"publisher-location":"Berlin, Heidelberg","reference-count":16,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540160427"},{"type":"electronic","value":"9783540397229"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1985]]},"DOI":"10.1007\/3-540-16042-6_28","type":"book-chapter","created":{"date-parts":[[2012,2,25]],"date-time":"2012-02-25T18:32:59Z","timestamp":1330194779000},"page":"496-503","source":"Crossref","is-referenced-by-count":28,"title":["NC algorithms for comparability graphs, interval graphs, and testing for unique perfect matching"],"prefix":"10.1007","author":[{"given":"Dexter","family":"Kozen","sequence":"first","affiliation":[]},{"given":"Umesh V.","family":"Vazirani","sequence":"additional","affiliation":[]},{"given":"Vijay V.","family":"Vazirani","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,5,29]]},"reference":[{"issue":"1\u20133","key":"28_CR1","doi-asserted-by":"publisher","first-page":"113","DOI":"10.1016\/S0019-9958(83)80060-6","volume":"58","author":"A. Borodin","year":"1983","unstructured":"A. Borodin, S.A. Cook, and N. Pippenger. \u201cParallel computation for well-endowed rings and space bounded probabilistic machines.\u201d Information and Control 58 1\u20133 (1983) 113\u2013136.","journal-title":"Information and Control"},{"key":"28_CR2","unstructured":"A. Borodin, J. von zur Gathen, and J. Hopcroft, \u201cFast parallel matrix and GCD computations. Prod. 23d STOC (1982) pp. 65\u201371."},{"key":"28_CR3","doi-asserted-by":"crossref","first-page":"400","DOI":"10.1145\/321707.321710","volume":"19","author":"S. Even","year":"1972","unstructured":"S. Even, A. Pnueli, and A. Lempel, \u201cPermutation graphs and transitive graphs,\u201d J. Assoc. Comput. Mach. 19 (1972), 400\u2013410.","journal-title":"J. Assoc. Comput. Mach."},{"key":"28_CR4","unstructured":"Fujii, M., Kasami, T., and Ninomiya K. \u201cOptimal Sequencing of Two Equivalent Processors,\u201d SIAM J. of Computing"},{"key":"28_CR5","doi-asserted-by":"crossref","first-page":"539","DOI":"10.4153\/CJM-1964-055-5","volume":"16","author":"P. C. Gilmore","year":"1964","unstructured":"Gilmore, P.C., and Hoffman, A.J. \u201cA Characterization of Comparability Graphs and of Interval Graphs,\u201d Canad. J. Math. 16 (1964), 539\u2013548.","journal-title":"Canad. J. Math."},{"key":"28_CR6","first-page":"1370","volume":"254","author":"A. Ghouila-Houri","year":"1962","unstructured":"A. Ghouila-Houri, Caracterisation des graphes nonorientes dont on peut orienter les aretes de maniere a obtenir le graphe d'une relation d'ordre,\u201d C.R. Acad. Sci. Paris 254 (1962), 1370\u20131371.","journal-title":"C.R. Acad. Sci. Paris"},{"issue":"1","key":"28_CR7","doi-asserted-by":"publisher","first-page":"68","DOI":"10.1016\/0095-8956(77)90049-1","volume":"22","author":"M. C. Golumbic","year":"1977","unstructured":"M.C. Golumbic, \u201cComparability Graphs and a New Matroid,\u201d J. Combinatorial Theory, Feb. 1977, Vol. 22, No. 1, 68\u201390.","journal-title":"J. Combinatorial Theory"},{"key":"28_CR8","unstructured":"D. Helmbold and E. Mayr, \u201cTwo Processor Scheduling is in NC,\u201d to appear."},{"key":"28_CR9","doi-asserted-by":"crossref","unstructured":"Karp, R.M., Upfal, E., and Wigderson, A. \u201cFinding a Maximum Matching is in Random NC,\u201d STOC (1985), 22\u201332.","DOI":"10.1145\/22145.22148"},{"key":"28_CR10","doi-asserted-by":"crossref","unstructured":"R.M. Karp and A. Wigderson, \u201cA Fast Parallel Algorithm for the Maximal Independent Set Problem,\u201d STOC (1984), 266\u2013272.","DOI":"10.1145\/800057.808690"},{"key":"28_CR11","unstructured":"Lovasz, L. \u201cOn Determinants, Matchings, and Random Algorithms,\u201d To appear."},{"key":"28_CR12","doi-asserted-by":"crossref","unstructured":"M. Luby, \u201cA Simple Parallel Algorithm for the Maximal Independent Set Problem,\u201d STOC (1985), 1\u201310.","DOI":"10.1145\/22145.22146"},{"key":"28_CR13","doi-asserted-by":"crossref","first-page":"160","DOI":"10.4153\/CJM-1971-016-5","volume":"23","author":"A. Pnueli","year":"1971","unstructured":"A. Pnueli, A. Lempel, and S. Even, \u201cTransitive orientation of graphs and identification of permutation graphs,\u201d Canad. J. Math. 23 (1971), 160\u2013175.","journal-title":"Canad. J. Math."},{"key":"28_CR14","volume-title":"\u201cMaximum Matchings in General Graphs through Randomization,\u201d Report No. TR15-84","author":"M. O. Rabin","year":"1984","unstructured":"Rabin, M.O., and Vazirani, V.V. \u201cMaximum Matchings in General Graphs through Randomization,\u201d Report No. TR15-84, Center for Research in Computing Technology, Harvard University, Cambridge, Massachusetts (1984)."},{"key":"28_CR15","doi-asserted-by":"crossref","first-page":"314","DOI":"10.4153\/CJM-1952-028-2","volume":"4","author":"W. T. Tutte","year":"1952","unstructured":"W.T. Tutte. \u201cThe factors of graphs.\u201d Canad. J. Math. 4 (1952) pp. 314\u2013328.","journal-title":"Canad. J. Math."},{"key":"28_CR16","doi-asserted-by":"crossref","unstructured":"U.V. Vazirani and V.V. Vazirani, \u201cThe Two-Processor Scheduling Problem is in Random NC,\u201d STOC (1985), 11\u201321.","DOI":"10.1145\/22145.22147"}],"container-title":["Lecture Notes in Computer Science","Foundations of Software Technology and Theoretical Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-16042-6_28.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,21]],"date-time":"2025-03-21T20:24:34Z","timestamp":1742588674000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-16042-6_28"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1985]]},"ISBN":["9783540160427","9783540397229"],"references-count":16,"URL":"https:\/\/doi.org\/10.1007\/3-540-16042-6_28","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1985]]}}}