{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T23:07:39Z","timestamp":1725664059116},"publisher-location":"Berlin, Heidelberg","reference-count":27,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540578994"},{"type":"electronic","value":"9783540483854"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1994]]},"DOI":"10.1007\/3-540-57899-4_41","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T13:41:18Z","timestamp":1330263678000},"page":"57-69","source":"Crossref","is-referenced-by-count":1,"title":["Algorithms and complexity of sandwich problems in graphs (extended abstract)"],"prefix":"10.1007","author":[{"given":"Martin Charles","family":"Golumbic","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Haim","family":"Kaplan","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ron","family":"Shamir","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,5,26]]},"reference":[{"issue":"3","key":"6_CR1","doi-asserted-by":"crossref","first-page":"121","DOI":"10.1016\/0020-0190(79)90002-4","volume":"8","author":"B. Apsvall","year":"1979","unstructured":"B. Apsvall, M. F. Plass, and R. Tarjan. A linear-time algorithm for testing the truth of certain quantified boolean formulas. Information Processing letters, 8(3): 121\u2013123, 1979.","journal-title":"Information Processing letters"},{"key":"6_CR2","series-title":"Lecture Notes in Computer Science, Vol. 623","doi-asserted-by":"crossref","first-page":"273","DOI":"10.1007\/3-540-55719-9_80","volume-title":"Proc. 19th 1CALP","author":"H. L. Bodlaender","year":"1992","unstructured":"H. L. Bodlaender, M. R. Fellows, and T. J. Warnow. Two strikes against perfect phylogeny. In W. Kuich, editor, Proc. 19th 1CALP, pages 273\u2013283, Berlin, 1992. Springer. Lecture Notes in Computer Science, Vol. 623."},{"key":"6_CR3","unstructured":"A. Brandst\u00e4dt. Special graph classes \u2014 a. survey. Technical Report SM-DU-199, Universit\u00e4t Duisburg, 1991."},{"key":"6_CR4","doi-asserted-by":"crossref","first-page":"205","DOI":"10.1016\/0012-365X(74)90002-8","volume":"9","author":"P. Buneman","year":"1974","unstructured":"P. Buneman. A characterization of rigid circuit graphs. Discrete Math., 9:205\u2013212, 1974.","journal-title":"Discrete Math."},{"key":"6_CR5","doi-asserted-by":"crossref","unstructured":"A. V. Carrano. Establishing the order of human chromosome-specific DNA fragments. In A. D. W\u00f6odhead and B. J. Barnhart, editors, Biotechnology and the Human Genome, pages 37\u201350. Plenum Press, 1988.","DOI":"10.1007\/978-1-4684-5547-2_5"},{"key":"6_CR6","doi-asserted-by":"crossref","first-page":"145","DOI":"10.1016\/S0167-5060(08)70731-3","volume":"1","author":"V. Chv\u00e1tal","year":"1977","unstructured":"V. Chv\u00e1tal and P. L. Hammer. Aggregation of inequalities for integer programming. Ann. Discrete Math., 1:145\u2013162, 1977.","journal-title":"Ann. Discrete Math."},{"key":"6_CR7","doi-asserted-by":"crossref","first-page":"163","DOI":"10.1016\/0166-218X(81)90013-5","volume":"3","author":"D. G. Corneil","year":"1981","unstructured":"D. G. Corneil, H. Lerchs, and L. Stewart Burlingham. Complement reducible graphs. Discrete Applied mathematics, 3:163\u2013174, 1981.","journal-title":"Discrete Applied mathematics"},{"key":"6_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 Math. Acad. Sci. Hungar., 18:25\u201366, 1967.","journal-title":"Acta Math. Acad. Sci. Hungar."},{"key":"6_CR9","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"M. R. Garey","year":"1979","unstructured":"M. R. Garey and D. S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman and co.. San Francisco, 1979."},{"key":"6_CR10","doi-asserted-by":"crossref","first-page":"237","DOI":"10.1016\/0012-365X(75)90021-7","volume":"13","author":"F. Gavril","year":"1975","unstructured":"F. Gavril. A recognition algorithm for the intersection graphs of directed paths in directed trees. Discrete Math., 13:237\u2013249, 1975.","journal-title":"Discrete Math."},{"key":"6_CR11","doi-asserted-by":"crossref","first-page":"211","DOI":"10.1016\/0012-365X(78)90003-1","volume":"23","author":"F. Gavril","year":"1978","unstructured":"F. Gavril. A recognition algorithm for the intersection graphs of paths in trees. Discrete Math., 23:211\u2013227, 1978.","journal-title":"Discrete Math."},{"key":"6_CR12","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":"6_CR13","unstructured":"M. C. Golumbic, H. Kaplan, and R. Shamir. Graph sandwich problems. Technical Report 270-92, Computer Science Dept., Tel Aviv University, 1992. submitted."},{"key":"6_CR14","unstructured":"M. C. Golumbic, H. Kaplan, and R. Shamir. On the complexity of DNA physical mapping. Technical Report. 271-93, Computer Science Dept., Tel Aviv University, 1993. To appear in Advances in Applied Mathematics."},{"key":"6_CR15","doi-asserted-by":"crossref","first-page":"37","DOI":"10.1016\/0012-365X(83)90019-5","volume":"43","author":"M. C. Golumbic","year":"1983","unstructured":"M. C. Golumbic, D. Rotem, and J. Urrutia. Comparability graphs and intersection graphs. Discrete Math., 43:37\u201346, 1983.","journal-title":"Discrete Math."},{"key":"6_CR16","volume-title":"Technical Report 91-54","author":"M. C. Golumbic","year":"1991","unstructured":"M. C. Golumbic and R. Shamir. Complexity and algorithms for reasoning about time: A graph-theoretic approach. Technical Report 91-54, DIMACS Center, Rutgers University, NJ, 1991. to appear in JACM."},{"key":"6_CR17","doi-asserted-by":"crossref","unstructured":"P. L. Hammer, T. Ibaraki, and U. N. Peled. Threshold numbers and threshold completions. In P. Hansen, editor, Studies on Graphs and Discrete Programming, pages 125\u2013145. North-Holland, 1981.","DOI":"10.1016\/S0304-0208(08)73462-5"},{"key":"6_CR18","doi-asserted-by":"crossref","first-page":"434","DOI":"10.1016\/0196-6774(85)90012-4","volume":"6","author":"D. S. Johnson","year":"1985","unstructured":"D. S. Johnson. The NP-completeness column: an ongoing guide. J. of Algorithms, 6:434\u2013451, 1985.","journal-title":"J. of Algorithms"},{"issue":"2","key":"6_CR19","doi-asserted-by":"crossref","first-page":"249","DOI":"10.1137\/0405019","volume":"5","author":"S. K. Kannan","year":"1992","unstructured":"S. K. Kannan and T. J. Warnow. Triangulating 3-colored graphs. SIAM J. of Discrete Math., 5(2):249\u2013258, 1992.","journal-title":"SIAM J. of Discrete Math."},{"issue":"1","key":"6_CR20","doi-asserted-by":"crossref","first-page":"111","DOI":"10.1137\/0208008","volume":"8","author":"J. Opatrny","year":"1979","unstructured":"J. Opatrny. Total ordering problems. SIAM J. Computing, 8(1):111\u2013114, 1979.","journal-title":"SIAM J. Computing"},{"key":"6_CR21","volume-title":"Discrete Mathematical Models, with Applications to Social Biological and Environmental Problems","author":"F. S. Roberts","year":"1976","unstructured":"F. S. Roberts. Discrete Mathematical Models, with Applications to Social Biological and Environmental Problems. Prentice-Hall, Englewood Cliffs, New Jersey, 1976."},{"key":"6_CR22","doi-asserted-by":"crossref","first-page":"183","DOI":"10.1016\/B978-1-4832-3187-7.50018-0","volume-title":"Graph Theory and Computing","author":"J. D. Rose","year":"1972","unstructured":"J. D. Rose. A graph-theoretic study of the numerical solution of sparse positive definite systems of linear equations. In R. C. Reed, editor, Graph Theory and Computing, pages 183\u2013217. Academic Press. N.Y., 1972."},{"key":"6_CR23","doi-asserted-by":"crossref","first-page":"429","DOI":"10.1002\/net.3230120407","volume":"11","author":"D. Rotem","year":"1982","unstructured":"D. Rotem and J. Urrutia. Circular permutation graphs. Networks, 11:429\u2013437, 1982.","journal-title":"Networks"},{"key":"6_CR24","doi-asserted-by":"crossref","unstructured":"T. J. Schaefer. The complexity of satisfiability problems. In Proc. 10th Annual ACM Symp. on Theory of Computing, pages 216\u2013226, 1978.","DOI":"10.1145\/800133.804350"},{"key":"6_CR25","doi-asserted-by":"crossref","first-page":"91","DOI":"10.1007\/BF02618470","volume":"9","author":"M. Steel","year":"1992","unstructured":"M. Steel. The complexity of reconstructing trees from qualitative characters and subtrees. J. of Classification, 9:91\u2013116, 1992.","journal-title":"J. of Classification"},{"key":"6_CR26","doi-asserted-by":"crossref","first-page":"1257","DOI":"10.1090\/S0002-9904-1970-12628-3","volume":"76","author":"A. C. Tucker","year":"1970","unstructured":"A. C. Tucker. Characterizing circular arc graphs. Bull. Amer. Math. Soc., 76:1257\u20131260, 1970.","journal-title":"Bull. Amer. Math. Soc."},{"key":"6_CR27","doi-asserted-by":"crossref","unstructured":"M. Yannakakis. Computing the minimum fill-in is NP-complet. e. SIAM J. Alg. Disc. Meth., 2, 1981.","DOI":"10.1137\/0602010"}],"container-title":["Lecture Notes in Computer Science","Graph-Theoretic Concepts in Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-57899-4_41.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T21:15:42Z","timestamp":1605647742000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-57899-4_41"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1994]]},"ISBN":["9783540578994","9783540483854"],"references-count":27,"URL":"https:\/\/doi.org\/10.1007\/3-540-57899-4_41","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1994]]}}}