{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,9]],"date-time":"2026-04-09T06:40:47Z","timestamp":1775716847475,"version":"3.50.1"},"publisher-location":"Berlin, Heidelberg","reference-count":13,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540542339","type":"print"},{"value":"9783540475163","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1991]]},"DOI":"10.1007\/3-540-54233-7_180","type":"book-chapter","created":{"date-parts":[[2012,2,25]],"date-time":"2012-02-25T22:39:34Z","timestamp":1330209574000},"page":"751-762","source":"Crossref","is-referenced-by-count":24,"title":["Ordering problems approximated: single-processor scheduling and interval graph completion"],"prefix":"10.1007","author":[{"given":"R.","family":"Ravi","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ajit","family":"Agrawal","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Philip","family":"Klein","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,6,8]]},"reference":[{"key":"60_CR1","doi-asserted-by":"crossref","first-page":"403","DOI":"10.1137\/0125042","volume":"25","author":"D. Adolphson","year":"1973","unstructured":"D. Adolphson and T. C. Hu, \u201cOptimal linear ordering\u201d, SIAM J. Appl. Math. 25 (1973), pp. 403\u2013423.","journal-title":"SIAM J. Appl. Math."},{"key":"60_CR2","volume-title":"Theory of Scheduling","author":"R. W. Conway","year":"1967","unstructured":"R. W. Conway, W. L. Maxwell, and L. W. Miller, Theory of Scheduling (1967), Addison-Wesley, Reading, Massachusetts."},{"key":"60_CR3","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, San Francisco (1979)."},{"key":"60_CR4","doi-asserted-by":"crossref","first-page":"237","DOI":"10.1016\/0304-3975(76)90059-1","volume":"1","author":"M. R. Garey","year":"1976","unstructured":"M. R. Garey., D. S. Johnson, and L. Stockmeyer, \u201cSome simplified NP-complete graph problems,\u201d Theor. Comput. Sci. 1 (1976), pp. 237\u2013267.","journal-title":"Theor. Comput. Sci."},{"key":"60_CR5","doi-asserted-by":"crossref","unstructured":"Mark D. Hansen, \u201cApproximation algorithms for geometric embeddings in the plane with applications to parallel processing problems,\u201d Proceedings, 30th Symposium on Foundations of Computer Science (1989), pp. 604\u2013609.","DOI":"10.1109\/SFCS.1989.63542"},{"key":"60_CR6","doi-asserted-by":"crossref","first-page":"189","DOI":"10.1137\/0123021","volume":"23","author":"W. A. Horn","year":"1972","unstructured":"W. A. Horn, \u201cSingle machine job sequencing with treelike precedence ordering and linear delay penalties,\u201d SIAM J. Appl. Math. 23 (1972), pp. 189\u2013202.","journal-title":"SIAM J. Appl. Math."},{"key":"60_CR7","doi-asserted-by":"crossref","first-page":"565","DOI":"10.2140\/pjm.1969.28.565","volume":"28","author":"D. G. Kendall","year":"1969","unstructured":"D. G. Kendall, \u201cIncidence matrices, interval graphs, and seriation in archeology,\u201d Pacific J. Math. 28 (1969), pp. 565\u2013570.","journal-title":"Pacific J. Math."},{"key":"60_CR8","doi-asserted-by":"crossref","unstructured":"P. Klein, A. Agrawal, R. Ravi, and S. Rao, \u201cApproximation through multicommodity flow\u201d, Proceedings, 31st Annual Symp. on Foundations of Comp. Sci., (1990), pp. 726\u2013737.","DOI":"10.1109\/FSCS.1990.89595"},{"key":"60_CR9","doi-asserted-by":"crossref","first-page":"75","DOI":"10.1016\/S0167-5060(08)70323-6","volume":"2","author":"E. L. Lawler","year":"1978","unstructured":"E. L. Lawler, \u201cSequencing jobs to minimize total weighted completion time subject to precedence constraints,\u201d Annals of Discrete Math. 2 (1978), pp. 75\u201390.","journal-title":"Annals of Discrete Math."},{"key":"60_CR10","doi-asserted-by":"crossref","unstructured":"F. T. Leighton, F. Makedon, S. Plotkin, C. Stein, E. Tardos, S. Tragoudas, \u201cFast approximation algorithms for multicommodity flow problems,\u201d Proceedings, 23rd Annual ACM Symposium on Theory of Computing (1991), to appear.","DOI":"10.1145\/103418.103425"},{"key":"60_CR11","unstructured":"F. T. Leighton, F. Makedon, and S. Tragoudas, personal communication, 1990"},{"key":"60_CR12","doi-asserted-by":"crossref","unstructured":"F. T. Leighton and S. Rao, \u201cAn approximate max-flow min-cut theorem for uniform multicommodity flow problems with application to approximation algorithms\u201d, Proceedings, 29th Symposium on Foundations of Computer Science (1988), pp. 422\u2013431.","DOI":"10.1109\/SFCS.1988.21958"},{"key":"60_CR13","doi-asserted-by":"crossref","first-page":"271","DOI":"10.1016\/0020-0190(88)90091-9","volume":"27","author":"G. Ramalingam","year":"1988","unstructured":"G. Ramalingam, and C. Pandu Rangan, \u201cA unified approach to domination problems in interval graphs\u201d, Information Processing Letters, vol. 27 (1988), pp. 271\u2013274.","journal-title":"Information Processing Letters"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-54233-7_180.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,28]],"date-time":"2021-04-28T01:20:26Z","timestamp":1619572826000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-54233-7_180"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1991]]},"ISBN":["9783540542339","9783540475163"],"references-count":13,"URL":"https:\/\/doi.org\/10.1007\/3-540-54233-7_180","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[1991]]}}}