{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,10,23]],"date-time":"2023-10-23T12:25:33Z","timestamp":1698063933163},"reference-count":62,"publisher":"Elsevier BV","issue":"2","license":[{"start":{"date-parts":[[1983,6,1]],"date-time":"1983-06-01T00:00:00Z","timestamp":423273600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Journal of Algorithms"],"published-print":{"date-parts":[[1983,6]]},"DOI":"10.1016\/0196-6774(83)90045-7","type":"journal-article","created":{"date-parts":[[2005,2,10]],"date-time":"2005-02-10T08:44:36Z","timestamp":1108025076000},"page":"189-203","source":"Crossref","is-referenced-by-count":27,"title":["The NP-completeness column: An ongoing guide"],"prefix":"10.1016","volume":"4","author":[{"given":"David S","family":"Johnson","sequence":"first","affiliation":[]}],"member":"78","reference":[{"key":"10.1016\/0196-6774(83)90045-7_BIB1","series-title":"Proceedings 19th Ann. Symp. on Foundations of Computer Science","first-page":"75","article-title":"Two theorems on random polynomial time","author":"Adleman","year":"1978"},{"key":"10.1016\/0196-6774(83)90045-7_BIB2","series-title":"The Design and Analysis of Computer Algorithms","author":"Aho","year":"1974"},{"key":"10.1016\/0196-6774(83)90045-7_BIB3","series-title":"Proceedings 14th Ann. ACM Symp. on Theory of Computing","first-page":"345","article-title":"Graph problems on a mesh-connected processor array","author":"Atallah","year":"1982"},{"key":"10.1016\/0196-6774(83)90045-7_BIB4","doi-asserted-by":"crossref","first-page":"51","DOI":"10.1016\/0196-6774(80)90004-8","article-title":"A parallel algorithm for constructing minimum spanning trees","volume":"1","author":"Bentley","year":"1980","journal-title":"J. Algorithms"},{"key":"10.1016\/0196-6774(83)90045-7_BIB5","doi-asserted-by":"crossref","first-page":"60","DOI":"10.1016\/0020-0190(79)90143-1","article-title":"Deadline scheduling of tasks with ready times and resource constraints","volume":"8","author":"Blazewics","year":"1979","journal-title":"Inform. Process. Lett."},{"key":"10.1016\/0196-6774(83)90045-7_BIB6","series-title":"A polynomial in time algorithm for task scheduling under fixed resource constraints","author":"Blazewics","year":"1980"},{"key":"10.1016\/0196-6774(83)90045-7_BIB7","doi-asserted-by":"crossref","first-page":"11","DOI":"10.1016\/0166-218X(83)90012-4","article-title":"Scheduling subject to resource constraints: Classification and complexity","volume":"5","author":"Blazewicz","year":"1983","journal-title":"Disc. Applied Math."},{"key":"10.1016\/0196-6774(83)90045-7_BIB8","doi-asserted-by":"crossref","first-page":"215","DOI":"10.1016\/0304-3975(76)90057-8","article-title":"Translational lemmas, polynomial time, and (logn)j-space","volume":"1","author":"Book","year":"1976","journal-title":"Theor. Comput. Sci."},{"key":"10.1016\/0196-6774(83)90045-7_BIB9","doi-asserted-by":"crossref","first-page":"733","DOI":"10.1137\/0206054","article-title":"On relating time and space to size and depth","volume":"6","author":"Borodin","year":"1977","journal-title":"SIAM J. Comput."},{"key":"10.1016\/0196-6774(83)90045-7_BIB10","series-title":"Proceedings 14th Ann. ACM Symp. on Theory of Computing","first-page":"338","article-title":"Routing, merging and sorting on parallel models of computation","author":"Borodin","year":"1982"},{"key":"10.1016\/0196-6774(83)90045-7_BIB11","doi-asserted-by":"crossref","first-page":"114","DOI":"10.1145\/322234.322243","article-title":"Alternation","volume":"28","author":"Chandra","year":"1981","journal-title":"J. Assoc. Comput. Mach."},{"key":"10.1016\/0196-6774(83)90045-7_BIB12","series-title":"Proceedings 17th Ann. Symp. on Foundations of Computer Science","first-page":"98","article-title":"Alternation","author":"Chandra","year":"1976"},{"key":"10.1016\/0196-6774(83)90045-7_BIB13","series-title":"Proceedings 23rd Ann. Symp. on Foundations of Computer Science","first-page":"1","article-title":"A complexity theory for unbounded fan-in parallelism","author":"Chandra","year":"1982"},{"key":"10.1016\/0196-6774(83)90045-7_BIB14","series-title":"Proceedings 11th Ann. ACM Symp. on Theory of Computing","first-page":"338","article-title":"Deterministic CFL's are accepted simultaneously in polynomial time and log squared space","author":"Cook","year":"1979"},{"key":"10.1016\/0196-6774(83)90045-7_BIB15","article-title":"Towards a complexity theory of synchronous parallel computation","author":"Cook","year":"1980"},{"key":"10.1016\/0196-6774(83)90045-7_BIB16","doi-asserted-by":"crossref","first-page":"657","DOI":"10.1137\/0210049","article-title":"Parallel matrix and graph algorithms","author":"Dekel","year":"1981","journal-title":"SIAM J. Comput."},{"key":"10.1016\/0196-6774(83)90045-7_BIB17","doi-asserted-by":"crossref","first-page":"24","DOI":"10.1287\/opre.31.1.24","article-title":"Parallel scheduling algorithms","volume":"31","author":"Dekel","year":"1983","journal-title":"Operations Res."},{"key":"10.1016\/0196-6774(83)90045-7_BIB18","doi-asserted-by":"crossref","first-page":"96","DOI":"10.1016\/0020-0190(79)90152-2","article-title":"Linear programming is log-space hard for P","volume":"8","author":"Dobkin","year":"1979","journal-title":"Inform. Process. Lett."},{"key":"10.1016\/0196-6774(83)90045-7_BIB19","series-title":"Procrastination pays: A mixed scheduling strategy","author":"Dolev","year":"1982"},{"key":"10.1016\/0196-6774(83)90045-7_BIB20","article-title":"Scheduling precedence graphs of bounded height","author":"Dolev","year":"1982"},{"key":"10.1016\/0196-6774(83)90045-7_BIB21","series-title":"Proceedings 21 st Ann. Symp. on Foundations of Computer Science","first-page":"360","article-title":"Hardware complexity and parallel computation","author":"Dymond","year":"1980"},{"key":"10.1016\/0196-6774(83)90045-7_BIB22","series-title":"Proceedings 10th Ann. ACM Symp. on Theory of Computing","first-page":"114","article-title":"Parallelism in random access machines","author":"Fortune","year":"1978"},{"key":"10.1016\/0196-6774(83)90045-7_BIB23","doi-asserted-by":"crossref","first-page":"766","DOI":"10.1145\/322326.322335","article-title":"An almost-linear algorithm for two-processor scheduling","volume":"29","author":"Gabow","year":"1982","journal-title":"J. Assoc. Comput. Mach."},{"key":"10.1016\/0196-6774(83)90045-7_BIB24","article-title":"Exact and approximate algorithms for scheduling UET systems on two uniform processors","author":"Gabow","year":"1982"},{"key":"10.1016\/0196-6774(83)90045-7_BIB25","series-title":"Proceedings 15th Ann. ACM Symp. on Theory of Computing","first-page":"244","article-title":"A linear time algorithm for a special case of disjoint set union","author":"Gabow","year":"1983"},{"key":"10.1016\/0196-6774(83)90045-7_BIB26","doi-asserted-by":"crossref","first-page":"1073","DOI":"10.1145\/322344.322353","article-title":"A universal connection pattern for parallel computers","volume":"29","author":"Goldschlager","year":"1982","journal-title":"J. Assoc. Comput. Mach."},{"key":"10.1016\/0196-6774(83)90045-7_BIB27","doi-asserted-by":"crossref","first-page":"105","DOI":"10.1016\/0304-3975(82)90092-5","article-title":"The maximum flow problem is log-space complete for P","volume":"21","author":"Goldschlager","year":"1982","journal-title":"Theor. Comput. Sci."},{"key":"10.1016\/0196-6774(83)90045-7_BIB28","doi-asserted-by":"crossref","first-page":"287","DOI":"10.1016\/S0167-5060(08)70356-X","article-title":"Optimization and approximation in deterministic sequencing and scheduling: A survey","volume":"5","author":"Graham","year":"1979","journal-title":"Ann. Discrete Math."},{"key":"10.1016\/0196-6774(83)90045-7_BIB29","series-title":"Proceedings 21st Ann. Symp. on Foundations of Computer Science","first-page":"348","article-title":"On similarity and duality of computation","author":"Hong","year":"1980"},{"key":"10.1016\/0196-6774(83)90045-7_BIB30","series-title":"Proceedings 23rd Ann. Symp. on Foundations of Computer Science","first-page":"244","article-title":"Parallel algorithms for minimum cuts and maximum flows in planar networks","author":"Johnson","year":"1982"},{"key":"10.1016\/0196-6774(83)90045-7_BIB31","series-title":"Proceedings 12th Ann. ACM Symp. on Theory of Computing","first-page":"302","article-title":"Some connections between nonuniform and uniform complexity classes","author":"Karp","year":"1980"},{"key":"10.1016\/0196-6774(83)90045-7_BIB32","doi-asserted-by":"crossref","first-page":"817","DOI":"10.1145\/358690.363066","article-title":"Computer aided complexity classification of combinatorial problems","volume":"25","author":"Lageweg","year":"1982","journal-title":"Comm. ACM"},{"key":"10.1016\/0196-6774(83)90045-7_BIB33","article-title":"Computer aided complexity classification of deterministic scheduling problems","author":"Lageweg","year":"1981"},{"key":"10.1016\/0196-6774(83)90045-7_BIB34","article-title":"Preemptive scheduling of uniform processors with memory","author":"Lai","year":"1982"},{"key":"10.1016\/0196-6774(83)90045-7_BIB35","article-title":"Preemptive scheduling of precedence-constrained jobs on parallel machines","author":"Lawler","year":"1981"},{"key":"10.1016\/0196-6774(83)90045-7_BIB36","series-title":"Preemptive scheduling of uniform parallel machines to minimize the number of late jobs","author":"Lawler","year":"1981"},{"key":"10.1016\/0196-6774(83)90045-7_BIB37","doi-asserted-by":"crossref","first-page":"612","DOI":"10.1145\/322092.322101","article-title":"On preemptive scheduling of unrelated parallel processors by linear programming","volume":"25","author":"Lawler","year":"1978","journal-title":"J. Assoc. Comput. Mach."},{"key":"10.1016\/0196-6774(83)90045-7_BIB38","article-title":"Recent developments in deterministic sequencing and scheduling: A survey","author":"Lawler","year":"1981"},{"key":"10.1016\/0196-6774(83)90045-7_BIB39","first-page":"1","article-title":"A gift for Alexander: At play in the fields of scheduling theory","volume":"7","author":"Lawler","year":"1982","journal-title":"Optima: Mathematical Programming Society Newsletter"},{"key":"10.1016\/0196-6774(83)90045-7_BIB40","doi-asserted-by":"crossref","first-page":"9","DOI":"10.1016\/0020-0190(81)90066-1","article-title":"Scheduling periodically occurring tasks on multiple processors","volume":"12","author":"Lawler","year":"1981","journal-title":"Inform. Process. Lett."},{"key":"10.1016\/0196-6774(83)90045-7_BIB41","doi-asserted-by":"crossref","first-page":"163","DOI":"10.1287\/opre.30.1.163","article-title":"On scheduling independent tasks with restricted execution times","volume":"30","author":"Leung","year":"1982","journal-title":"Operations Res."},{"key":"10.1016\/0196-6774(83)90045-7_BIB42","doi-asserted-by":"crossref","first-page":"115","DOI":"10.1016\/0020-0190(80)90123-4","article-title":"A note on preemptive scheduling of periodic, real-time tasks","volume":"11","author":"Leung","year":"1980","journal-title":"Inform. Process. Lett."},{"key":"10.1016\/0196-6774(83)90045-7_BIB43","series-title":"On the complexity of fixed-priority scheduling of periodie, real-time tasks","author":"Leung","year":"1981"},{"key":"10.1016\/0196-6774(83)90045-7_BIB44","doi-asserted-by":"crossref","first-page":"189","DOI":"10.1287\/opre.29.1.189","article-title":"Concurrent task systems","volume":"29","author":"Lloyd","year":"1981","journal-title":"Operations Res."},{"key":"10.1016\/0196-6774(83)90045-7_BIB45","doi-asserted-by":"crossref","first-page":"812","DOI":"10.1145\/322326.322337","article-title":"Preemptive scheduling with release times, deadlines, and due times","volume":"29","author":"Martel","year":"1982","journal-title":"J. Assoc. Comput. Mach."},{"key":"10.1016\/0196-6774(83)90045-7_BIB46","article-title":"Well structured parallel programs are not easier to schedule","author":"Mayr","year":"1981"},{"key":"10.1016\/0196-6774(83)90045-7_BIB47","unstructured":"N. Megiddo, private communication (1982)."},{"key":"10.1016\/0196-6774(83)90045-7_BIB48","article-title":"On Nonpreemptive Multiprocessor Scheduling with Discrete Starting Times","author":"Nakajima","year":"1982"},{"key":"10.1016\/0196-6774(83)90045-7_BIB49","doi-asserted-by":"crossref","first-page":"344","DOI":"10.1016\/0196-6774(82)90030-X","article-title":"Complexity results for scheduling tasks with discrete starting times","volume":"3","author":"Nakajima","year":"1982","journal-title":"J. Algorithms"},{"key":"10.1016\/0196-6774(83)90045-7_BIB50","doi-asserted-by":"crossref","first-page":"512","DOI":"10.1137\/0211040","article-title":"Complexity results for scheduling tasks in fixed intervals on two types of machines","volume":"11","author":"Nakajima","year":"1982","journal-title":"SIAM J. Comput."},{"key":"10.1016\/0196-6774(83)90045-7_BIB51","series-title":"Proceedings 20th Ann. Symp. on Foundations of Computer Science","first-page":"307","article-title":"On simultaneous resource bounds","author":"Pippenger","year":"1979"},{"key":"10.1016\/0196-6774(83)90045-7_BIB52","doi-asserted-by":"crossref","first-page":"198","DOI":"10.1016\/S0022-0000(76)80037-2","article-title":"A characterization of the power of vector machines","volume":"12","author":"Pratt","year":"1978","journal-title":"J. Comput. System Sci."},{"key":"10.1016\/0196-6774(83)90045-7_BIB53_1","series-title":"Proceedings 20th Ann. Symp. on Foundations of Computer Science","first-page":"312","article-title":"On uniform circuit complexity","author":"Ruzzo","year":"1979"},{"key":"10.1016\/0196-6774(83)90045-7_BIB53_2","doi-asserted-by":"crossref","first-page":"365","DOI":"10.1016\/0022-0000(81)90038-6","volume":"22","author":"Ruzzo","year":"1981","journal-title":"J. Comput. System Sci."},{"key":"10.1016\/0196-6774(83)90045-7_BIB54","doi-asserted-by":"crossref","first-page":"682","DOI":"10.1137\/0210051","article-title":"Fast, efficient parallel algorithms for some graph problems","volume":"10","author":"Savage","year":"1981","journal-title":"SIAM J. Comput."},{"key":"10.1016\/0196-6774(83)90045-7_BIB55","doi-asserted-by":"crossref","first-page":"103","DOI":"10.1145\/322108.322119","article-title":"Time bounded random access machines with parallel computing","volume":"26","author":"Savitch","year":"1979","journal-title":"J. Assoc. Comput. Mach."},{"key":"10.1016\/0196-6774(83)90045-7_BIB56","series-title":"Proceedings 21st Ann. Symp. on Foundations of Computer Science","first-page":"50","article-title":"A fast algorithm for multiprocessor scheduling","author":"Simons","year":"1980"},{"key":"10.1016\/0196-6774(83)90045-7_BIB57","article-title":"On scheduling unit-time jobs with multiple release time\/deadline intervals","author":"Simons","year":"1981"},{"key":"10.1016\/0196-6774(83)90045-7_BIB58","doi-asserted-by":"crossref","first-page":"88","DOI":"10.1016\/0196-6774(81)90010-9","article-title":"Finding the maximum, merging, and sorting in a parallel computation model","volume":"2","author":"Shiloach","year":"1981","journal-title":"J. Algorithms"},{"key":"10.1016\/0196-6774(83)90045-7_BIB59","doi-asserted-by":"crossref","first-page":"57","DOI":"10.1016\/0196-6774(82)90008-6","article-title":"An O(logn) parallel connectivity algorithm","volume":"3","author":"Shiloach","year":"1982","journal-title":"J. Algorithms"},{"key":"10.1016\/0196-6774(83)90045-7_BIB60","doi-asserted-by":"crossref","first-page":"128","DOI":"10.1016\/0196-6774(82)90013-X","article-title":"An O(n2logn) parallel MAX-FLOW algorithm","volume":"3","author":"Shiloach","year":"1982","journal-title":"J. Algorithms"},{"key":"10.1016\/0196-6774(83)90045-7_BIB61","doi-asserted-by":"crossref","first-page":"348","DOI":"10.1137\/0204030","article-title":"Parallelism in comparison problems","volume":"4","author":"Valiant","year":"1975","journal-title":"SIAM J. Comput."}],"container-title":["Journal of Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:0196677483900457?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:0196677483900457?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2019,1,29]],"date-time":"2019-01-29T06:51:15Z","timestamp":1548744675000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/0196677483900457"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1983,6]]},"references-count":62,"journal-issue":{"issue":"2","published-print":{"date-parts":[[1983,6]]}},"alternative-id":["0196677483900457"],"URL":"https:\/\/doi.org\/10.1016\/0196-6774(83)90045-7","relation":{},"ISSN":["0196-6774"],"issn-type":[{"value":"0196-6774","type":"print"}],"subject":[],"published":{"date-parts":[[1983,6]]}}}