{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,7]],"date-time":"2025-10-07T04:47:38Z","timestamp":1759812458944},"reference-count":46,"publisher":"Elsevier BV","issue":"4","license":[{"start":{"date-parts":[[1982,12,1]],"date-time":"1982-12-01T00:00:00Z","timestamp":407548800000},"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":[[1982,12]]},"DOI":"10.1016\/0196-6774(82)90032-3","type":"journal-article","created":{"date-parts":[[2005,2,10]],"date-time":"2005-02-10T08:44:36Z","timestamp":1108025076000},"page":"381-395","source":"Crossref","is-referenced-by-count":28,"title":["The NP-completeness column: An ongoing gulde"],"prefix":"10.1016","volume":"3","author":[{"given":"David S","family":"Johnson","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"78","reference":[{"key":"10.1016\/0196-6774(82)90032-3_BIB1","article-title":"Complexity results for channel routing","author":"Arnold","year":"1982"},{"key":"10.1016\/0196-6774(82)90032-3_BIB2","article-title":"Complexity results for single-row routing","author":"Arnold","year":"1982"},{"key":"10.1016\/0196-6774(82)90032-3_BIB3","series-title":"A provably good algorithm for the two module routing problem","author":"Baker","year":"1982"},{"key":"10.1016\/0196-6774(82)90032-3_BIB4","series-title":"The \u201crace graph\u201d: an NP-complete problem","author":"Boers","year":"1982"},{"key":"10.1016\/0196-6774(82)90032-3_BIB5","series-title":"Proc. 13th Design Automation Conf.","first-page":"425","article-title":"A dogleg channel router","author":"Deutsch","year":"1976"},{"key":"10.1016\/0196-6774(82)90032-3_BIB6","series-title":"Proceedings 13th Ann. ACM Symp. on Theory of Computing","first-page":"312","article-title":"Optimal wiring between rectangles","author":"Dolev","year":"1981"},{"key":"10.1016\/0196-6774(82)90032-3_BIB7","unstructured":"J. Edmonds, unpublished results (1977)."},{"key":"10.1016\/0196-6774(82)90032-3_BIB8","doi-asserted-by":"crossref","first-page":"400","DOI":"10.1145\/321707.321710","article-title":"Permutation graphs and transitive graphs","volume":"19","author":"Even","year":"1972","journal-title":"J. Assoc. Comput. Mach."},{"key":"10.1016\/0196-6774(82)90032-3_BIB9","doi-asserted-by":"crossref","first-page":"43","DOI":"10.1016\/S0196-8858(82)80004-3","article-title":"The Steiner problem in phylogeny is NP-complete","volume":"3","author":"Foulds","year":"1982","journal-title":"Advances Appl. Math."},{"key":"10.1016\/0196-6774(82)90032-3_BIB10","doi-asserted-by":"crossref","first-page":"227","DOI":"10.1109\/TSE.1976.233819","article-title":"On two problems in the generation of program test paths","author":"Gabow","year":"1976","journal-title":"IEEE Trans. Software Engrg."},{"key":"10.1016\/0196-6774(82)90032-3_BIB11","doi-asserted-by":"crossref","first-page":"216","DOI":"10.1137\/0601025","article-title":"The complexity of coloring circular arcs and chords","volume":"1","author":"Garey","year":"1980","journal-title":"SIAM J. Algebraic and Discrete Methods"},{"key":"10.1016\/0196-6774(82)90032-3_BIB12","series-title":"Proc. 8th Design Automation Workshop","first-page":"155","article-title":"Wire routing by optimizing channel assignment within large apertures","author":"Hashimoto","year":"1971"},{"key":"10.1016\/0196-6774(82)90032-3_BIB13","article-title":"Wire-routing is NP-complete","author":"Kramer","year":"1982"},{"key":"10.1016\/0196-6774(82)90032-3_BIB14","doi-asserted-by":"crossref","first-page":"361","DOI":"10.1109\/TCS.1979.1084650","article-title":"On optimum single row routing","author":"Kuh","year":"1979","journal-title":"IEEE Trans. Circuits and Systems"},{"key":"10.1016\/0196-6774(82)90032-3_BIB15","series-title":"Proceedings 21st Ann. Symp. on Foundations of Computer Science","first-page":"282","article-title":"A polynomial time algorithm for optimal routing around a rectangle","author":"LaPaugh","year":"1980"},{"key":"10.1016\/0196-6774(82)90032-3_BIB16","article-title":"Algorithms for Integrated Circuit Layout: An Analytic Approach","author":"LaPaugh","year":"1980"},{"key":"10.1016\/0196-6774(82)90032-3_BIB17","doi-asserted-by":"crossref","unstructured":"A. S. LaPaugh and C. H. Papadimitriou, The even path problem for graphs and digraphs, Networds, to appear.","DOI":"10.1002\/net.3230140403"},{"key":"10.1016\/0196-6774(82)90032-3_BIB18","series-title":"VLSI Systems and computations","first-page":"126","article-title":"Optimal placement for river routing","author":"Leiserson","year":"1981"},{"key":"10.1016\/0196-6774(82)90032-3_BIB19","series-title":"Minimum perimeter partitions of planar figures","author":"Lingas","year":"1982"},{"key":"10.1016\/0196-6774(82)90032-3_BIB20","doi-asserted-by":"crossref","unstructured":"A. Mansfield, Determining the thickness of graphs is NP-hard, Math. Proc. Cambridge Phil. Soc., to appear.","DOI":"10.1017\/S030500410006028X"},{"key":"10.1016\/0196-6774(82)90032-3_BIB21","article-title":"Topics in Computational Complexity","author":"Mansfield","year":"1982"},{"key":"10.1016\/0196-6774(82)90032-3_BIB22","article-title":"On the complexity of point covering and line covering","author":"Megiddo","year":"1981"},{"key":"10.1016\/0196-6774(82)90032-3_BIB23","doi-asserted-by":"crossref","first-page":"520","DOI":"10.1109\/TSE.1979.234213","article-title":"On path cover problems in digraphs and applications to program testing","author":"Ntafos","year":"1979","journal-title":"IEEE Trans. Software Engrg."},{"key":"10.1016\/0196-6774(82)90032-3_BIB24","doi-asserted-by":"crossref","first-page":"67","DOI":"10.1109\/TC.1981.6312158","article-title":"On structured digraphs and program testing","author":"Ntafos","year":"1981","journal-title":"IEEE Trans. Computer"},{"key":"10.1016\/0196-6774(82)90032-3_BIB25","series-title":"VLSI Systems and computations","first-page":"160","article-title":"Optimal routing in rectilinear channels","author":"Pinter","year":"1981"},{"key":"10.1016\/0196-6774(82)90032-3_BIB26","series-title":"Proc. 1982 IEEE Int. Conf. on Circuits and Computers","article-title":"Optimal layer assignment for interconnect","author":"Pinter","year":"1982"},{"key":"10.1016\/0196-6774(82)90032-3_BIB27","unstructured":"R. Y. Pinter, private communication (1982)."},{"key":"10.1016\/0196-6774(82)90032-3_BIB28","article-title":"Manhattan and rectilinear wiring","author":"Raghaven","year":"1981"},{"key":"10.1016\/0196-6774(82)90032-3_BIB29","article-title":"Single row routing","author":"Raghaven","year":"1980"},{"key":"10.1016\/0196-6774(82)90032-3_BIB30","article-title":"The complexity of single row routing","author":"Raghaven","year":"1981"},{"key":"10.1016\/0196-6774(82)90032-3_BIB31","series-title":"Complexity of single-layer routing","author":"Richards","year":"1981"},{"key":"10.1016\/0196-6774(82)90032-3_BIB32","series-title":"VLSI Systems and computations","first-page":"153","article-title":"Provably good channel routing algorithms","author":"Rivest","year":"1981"},{"key":"10.1016\/0196-6774(82)90032-3_BIB33","series-title":"Proc. 7th Conf. on Graph Theoretic Concepts in Computer Science","first-page":"99","article-title":"Bus routing problems on acyclic networks","author":"R\u00f6ck","year":"1982"},{"key":"10.1016\/0196-6774(82)90032-3_BIB34","series-title":"VLSI Systems and computations","first-page":"143","article-title":"The separation for general single-layer wiring barriers","author":"Siegel","year":"1981"},{"key":"10.1016\/0196-6774(82)90032-3_BIB35","series-title":"Proc. IEEE Symp. on Circuits and Systems","first-page":"296","article-title":"Some theoretical results on the routing of multilayer printed wiring boards","author":"So","year":"1974"},{"key":"10.1016\/0196-6774(82)90032-3_BIB36","series-title":"Dogleg channel routing is NP-complete","author":"Szymanski","year":"1982"},{"key":"10.1016\/0196-6774(82)90032-3_BIB37","unstructured":"T.G. Szymanski and M. Yannakakis, private communication (1982)."},{"key":"10.1016\/0196-6774(82)90032-3_BIB38","series-title":"Proc. IEEE Symp. on Circuits and Systems","first-page":"902","article-title":"An approach to the routing of multilayer circuit boards","author":"Ting","year":"1978"},{"key":"10.1016\/0196-6774(82)90032-3_BIB39","doi-asserted-by":"crossref","first-page":"261","DOI":"10.1109\/TCS.1979.1084634","article-title":"Via assignment problem in multilayer printed circuit board","author":"Ting","year":"1979","journal-title":"IEEE Trans. Circuits and Systems"},{"key":"10.1016\/0196-6774(82)90032-3_BIB40","series-title":"Proceedings 12th Ann. ACM Symp. on Theory of Computing","first-page":"161","article-title":"An optimal solution to the wire-routing problem","author":"Tompa","year":"1980"},{"key":"10.1016\/0196-6774(82)90032-3_BIB41","doi-asserted-by":"crossref","first-page":"369","DOI":"10.1109\/TCS.1979.1084651","article-title":"An algorithm for the via assignment problem in multilayer backboard wiring","author":"Tsukiyama","year":"1979","journal-title":"IEEE Trans. Circuits and Systems"},{"key":"10.1016\/0196-6774(82)90032-3_BIB42","doi-asserted-by":"crossref","first-page":"287","DOI":"10.1002\/net.3230120307","article-title":"Double-row planar routing and permutation layout","volume":"12","author":"Tsukiyama","year":"1982","journal-title":"Networks"},{"key":"10.1016\/0196-6774(82)90032-3_BIB43","series-title":"Another NP-complete covering problem","author":"Van Emde Boas","year":"1982"},{"key":"10.1016\/0196-6774(82)90032-3_BIB44","article-title":"Komplexit\u00e4t von Wegproblemen in Graphen","author":"Vornberger","year":"1980"},{"key":"10.1016\/0196-6774(82)90032-3_BIB45","series-title":"Proceedings 13th Southeastern Conference on Combinatorics, Graph Theory, and Computing","article-title":"Steiner trees in outerplanar graphs","author":"Wald","year":"1982"},{"key":"10.1016\/0196-6774(82)90032-3_BIB46","series-title":"Steiner trees, partial 2-trees, and minimum IFI networks","author":"Wald","year":"1982"}],"container-title":["Journal of Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:0196677482900323?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:0196677482900323?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:37Z","timestamp":1548744697000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/0196677482900323"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1982,12]]},"references-count":46,"journal-issue":{"issue":"4","published-print":{"date-parts":[[1982,12]]}},"alternative-id":["0196677482900323"],"URL":"https:\/\/doi.org\/10.1016\/0196-6774(82)90032-3","relation":{},"ISSN":["0196-6774"],"issn-type":[{"value":"0196-6774","type":"print"}],"subject":[],"published":{"date-parts":[[1982,12]]}}}