{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,3,31]],"date-time":"2022-03-31T22:42:25Z","timestamp":1648766545207},"reference-count":18,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[1996,9,1]],"date-time":"1996-09-01T00:00:00Z","timestamp":841536000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[1996,9]]},"DOI":"10.1007\/bf01955675","type":"journal-article","created":{"date-parts":[[2005,8,1]],"date-time":"2005-08-01T15:15:58Z","timestamp":1122909358000},"page":"243-262","source":"Crossref","is-referenced-by-count":1,"title":["An NC algorithm for finding a minimum weighted completion time schedule on series parallel graphs"],"prefix":"10.1007","volume":"16","author":[{"given":"S.","family":"Sunder","sequence":"first","affiliation":[]},{"given":"Xin","family":"He","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"BF01955675_CR1","doi-asserted-by":"crossref","first-page":"287","DOI":"10.1016\/0196-6774(89)90017-5","volume":"10","author":"K. Abrahamson","year":"1987","unstructured":"K. Abrahamson, N. Dadoun, D. G. Kirkpatrick, and T. Przytycka, A simple parallel tree contraction algorithm,Journal of Algorithms,10 (1987), 287\u2013302.","journal-title":"Journal of Algorithms"},{"key":"BF01955675_CR2","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, Optimal linear ordering,SIAM Journal on Applied Mathematics,25 (1973), 403\u2013423.","journal-title":"SIAM Journal on Applied Mathematics"},{"key":"BF01955675_CR3","first-page":"147","volume-title":"LNCS, vol. 382","author":"M. Chrobak","year":"1989","unstructured":"M. Chrobak, J. Naor, and M. B. Novick, Using bounded degree spanning trees in the design of efficient algorithms on claw-free graphs,Proceedings of Workshop on Algorithms and Data Structures (LNCS, vol. 382), 1989, Springer-Verlag, Berlin, pp. 147\u2013163."},{"key":"BF01955675_CR4","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, Addison-Wesley, Reading, MA, 1967."},{"key":"BF01955675_CR5","doi-asserted-by":"crossref","first-page":"185","DOI":"10.1016\/0743-7315(84)90004-2","volume":"1","author":"E. Dekel","year":"1984","unstructured":"E. Dekel and S. Sahni, A parallel matching algorithm for convex bipartite graphs and applications toscheduling, Journal of Parallel and Distributed Computing,1 (1984), 185\u2013205.","journal-title":"Journal of Parallel and Distributed Computing"},{"key":"BF01955675_CR6","unstructured":"D. Dolev, E. Upfal, and M. Warmuth, Scheduling trees in parallel, inVLSI: Algorithms and Architectures, P. Bertolazzi and F. Luccio, eds., 1985."},{"key":"BF01955675_CR7","doi-asserted-by":"crossref","first-page":"287","DOI":"10.1016\/S0167-5060(08)70356-X","volume":"5","author":"R. L. Graham","year":"1979","unstructured":"R. L. Graham, E. L. Lawler, J. K. Lenstra, and A. H. G. R. Kan, Optimization and approximation in deterministic sequencing and scheduling: a survey,Annals of Discrete Mathematics,5 (1979), 287\u2013326.","journal-title":"Annals of Discrete Mathematics"},{"key":"BF01955675_CR8","doi-asserted-by":"crossref","first-page":"15","DOI":"10.1016\/0890-5401(87)90061-7","volume":"75","author":"X. He","year":"1987","unstructured":"X. He, Parallel recognition and decomposition of two terminal series parallel graphs,Information and Computation,75 (1987), 15\u201338.","journal-title":"Information and Computation"},{"key":"BF01955675_CR9","volume-title":"Advances in Computing Research","author":"D. Helmbold","year":"1987","unstructured":"D. Helmbold and E. Mayr, Fast scheduling algorithms on parallel computers, inAdvances in Computing Research, F. Preparata, ed., Jai Press, Greenwich, CT, 1987."},{"key":"BF01955675_CR10","doi-asserted-by":"crossref","first-page":"747","DOI":"10.1137\/0216050","volume":"16","author":"D. Helmbold","year":"1987","unstructured":"D. Helmbold and E. Mayr, Two processor scheduling is in NC,SIAM Journal on Computing,16 (1987), 747\u2013759.","journal-title":"SIAM Journal on Computing"},{"key":"BF01955675_CR11","doi-asserted-by":"crossref","first-page":"189","DOI":"10.1137\/0123021","volume":"23","author":"W. A. Horn","year":"1972","unstructured":"W. A. Horn, Single machine job sequencing with treelike precedence ordering and linear delay penalties,SIAM Journal on Applied Mathematics,23 (1972), 189\u2013202.","journal-title":"SIAM Journal on Applied Mathematics"},{"key":"BF01955675_CR12","doi-asserted-by":"crossref","unstructured":"H. Jung, P. Spirakis, and M. Sema, A parallel algorithm for two processors precedence constrained scheduling,Proceedings of 18th ICALP, 1991, pp. 417\u2013425.","DOI":"10.1007\/3-540-54233-7_152"},{"key":"BF01955675_CR13","first-page":"75","volume-title":"Annals of Discrete Mathematics, vol. 2","author":"E. L. Lawler","year":"1978","unstructured":"E. L. Lawler,Sequencing Jobs To Minimize Total Weighted Completion Time Subject to Precedence Constraints, Annals of Discrete Mathematics, vol. 2, North-Holland, Amsterdam, 1978, pp. 75\u201390."},{"key":"BF01955675_CR14","doi-asserted-by":"crossref","unstructured":"G. L. Miller and J. Reif, Parallel tree contraction and its application, inProceedings of 26th FOCS, 1985, pp. 478\u2013489.","DOI":"10.1109\/SFCS.1985.43"},{"key":"BF01955675_CR15","doi-asserted-by":"crossref","first-page":"283","DOI":"10.1287\/opre.23.2.283","volume":"23","author":"J. B. Sidney","year":"1975","unstructured":"J. B. Sidney, Decomposition algorithms for single-machine sequencing with precedence relations and deferral costs,Operations Research,23 (1975), 283\u2013298.","journal-title":"Operations Research"},{"key":"BF01955675_CR16","doi-asserted-by":"crossref","first-page":"59","DOI":"10.1002\/nav.3800030106","volume":"3","author":"W. E. Smith","year":"1956","unstructured":"W. E. Smith, Various optimizers for single stage production,Naval Research Logistics Quarterly,3 (1956), 59\u201366.","journal-title":"Naval Research Logistics Quarterly"},{"key":"BF01955675_CR17","doi-asserted-by":"crossref","first-page":"298","DOI":"10.1137\/0211023","volume":"11","author":"J. Valdez","year":"1982","unstructured":"J. Valdez, R. E. Tarjan, and E. L. Lawler, The recognition of series parallel graphs,SIAM Journal on Computing,11 (1982), 298\u2013313.","journal-title":"SIAM Journal on Computing"},{"key":"BF01955675_CR18","doi-asserted-by":"crossref","first-page":"1140","DOI":"10.1137\/0218076","volume":"18","author":"U. V. Vazirani","year":"1989","unstructured":"U. V. Vazirani and V. V. Vazirani, The two processor scheduling Is In random NC,SIAM Journal on Computing,18 (1989), 1140\u20131148.","journal-title":"SIAM Journal on Computing"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01955675.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF01955675\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01955675","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,4,8]],"date-time":"2020-04-08T14:24:54Z","timestamp":1586355894000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF01955675"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1996,9]]},"references-count":18,"journal-issue":{"issue":"3","published-print":{"date-parts":[[1996,9]]}},"alternative-id":["BF01955675"],"URL":"https:\/\/doi.org\/10.1007\/bf01955675","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[1996,9]]}}}