{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,28]],"date-time":"2025-09-28T20:43:56Z","timestamp":1759092236473},"reference-count":86,"publisher":"Elsevier BV","issue":"1","license":[{"start":{"date-parts":[[1984,3,1]],"date-time":"1984-03-01T00:00:00Z","timestamp":446947200000},"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":[[1984,3]]},"DOI":"10.1016\/0196-6774(84)90045-2","type":"journal-article","created":{"date-parts":[[2005,2,10]],"date-time":"2005-02-10T03:44:36Z","timestamp":1108007076000},"page":"147-160","source":"Crossref","is-referenced-by-count":39,"title":["The NP-completeness column: An ongoing guide"],"prefix":"10.1016","volume":"5","author":[{"given":"David S","family":"Johnson","sequence":"first","affiliation":[]}],"member":"78","reference":[{"key":"10.1016\/0196-6774(84)90045-2_BIB1","doi-asserted-by":"crossref","first-page":"37","DOI":"10.1002\/net.3230070104","article-title":"Rectilinear Steiner trees: efficient special case algorithms","volume":"7","author":"Aho","year":"1977","journal-title":"Networks"},{"key":"10.1016\/0196-6774(84)90045-2_BIB2","doi-asserted-by":"crossref","first-page":"228","DOI":"10.1016\/0020-0190(82)90021-7","article-title":"Complexity of finding k-path-free dominating sets in graphs","volume":"14","author":"Bar-Yehuda","year":"1982","journal-title":"Inform. Process. Lett."},{"key":"10.1016\/0196-6774(84)90045-2_BIB3","article-title":"Planar L1 tree layout","author":"Becker","year":"1980"},{"key":"10.1016\/0196-6774(84)90045-2_BIB4","series-title":"Generalized planar matching","author":"Berman","year":"1983"},{"key":"10.1016\/0196-6774(84)90045-2_BIB5","doi-asserted-by":"crossref","first-page":"157","DOI":"10.1016\/0020-0190(81)90048-X","article-title":"The edge Hamiltonian path problem is NP-complete","volume":"13","author":"Bertossi","year":"1981","journal-title":"Inform. Process. Lett."},{"key":"10.1016\/0196-6774(84)90045-2_BIB6","series-title":"Dominating sets for split and bipartite graphs","author":"Bertossi","year":"1982"},{"key":"10.1016\/0196-6774(84)90045-2_BIB7","doi-asserted-by":"crossref","first-page":"97","DOI":"10.1016\/0020-0190(83)90078-9","article-title":"Finding Hamiltonian circuits in proper interval graphs","volume":"17","author":"Bertossi","year":"1983","journal-title":"Inform. Process. Lett."},{"key":"10.1016\/0196-6774(84)90045-2_BIB8","series-title":"An NP-complete coloring problem in bipartite graphs","author":"Bertossi","year":"1983"},{"key":"10.1016\/0196-6774(84)90045-2_BIB9","series-title":"The complexity of minimizing wire lengths in VLSI layouts","author":"Bhatt","year":"1983"},{"key":"10.1016\/0196-6774(84)90045-2_BIB10","doi-asserted-by":"crossref","first-page":"35","DOI":"10.1007\/BFb0121193","article-title":"An algorithm for finding Hamiltonian circuits in certain graphs","volume":"8","author":"Bixby","year":"1978","journal-title":"Math. Programming Study"},{"key":"10.1016\/0196-6774(84)90045-2_BIB11","article-title":"Dominating sets and domatic number of circular arc graphs","author":"Bonuccelli","year":"1980"},{"key":"10.1016\/0196-6774(84)90045-2_BIB12","doi-asserted-by":"crossref","first-page":"191","DOI":"10.1137\/0211015","article-title":"Dominating sets in chordal graphs","volume":"11","author":"Booth","year":"1982","journal-title":"SIAM J. Comput."},{"key":"10.1016\/0196-6774(84)90045-2_BIB13","unstructured":"G. J. Chang, personal communication to M. Farber (1982)."},{"key":"10.1016\/0196-6774(84)90045-2_BIB14","article-title":"The k-domination and k-stability problem of graphs","author":"Chang","year":"1982"},{"key":"10.1016\/0196-6774(84)90045-2_BIB15","doi-asserted-by":"crossref","first-page":"214","DOI":"10.1016\/0167-6377(82)90024-4","article-title":"R-domination of block graphs","volume":"1","author":"Chang","year":"1982","journal-title":"Operations Res. Lett."},{"key":"10.1016\/0196-6774(84)90045-2_BIB16","series-title":"Proceedings 11th Ann. ACM Symp. on Theory of Computing","first-page":"38","article-title":"Decomposing a polygon into its convex parts","author":"Chazelle","year":"1979"},{"key":"10.1016\/0196-6774(84)90045-2_BIB17","doi-asserted-by":"crossref","first-page":"163","DOI":"10.1016\/0095-8956(72)90020-2","article-title":"On Hamilton's ideals","volume":"12","author":"Chav\u00e1tal","year":"1972","journal-title":"J. Combinatorial Theory"},{"key":"10.1016\/0196-6774(84)90045-2_BIB18","series-title":"Proceedings 19th Ann. Allerton Conf. on Communication, Control, and Computing","first-page":"741","article-title":"Some NP-complete problems on graphy decompositions","author":"Colbourn","year":"1981"},{"key":"10.1016\/0196-6774(84)90045-2_BIB19","doi-asserted-by":"crossref","first-page":"139","DOI":"10.1016\/0167-6377(82)90016-5","article-title":"Packing subgraphs of a graph","volume":"1","author":"Cornuejols","year":"1982","journal-title":"Operations Res. Lett."},{"key":"10.1016\/0196-6774(84)90045-2_BIB20","article-title":"An Optimistic Protocol for Partitioned Distributed Database Systems","author":"Davidson","year":"1982"},{"key":"10.1016\/0196-6774(84)90045-2_BIB21","series-title":"Technical Report","article-title":"On the complexity of partitioning graphs into connected subgraphs","author":"Dyer","year":"1983"},{"key":"10.1016\/0196-6774(84)90045-2_BIB22","series-title":"Planar three-dimensional matching","author":"Dyer","year":"1983"},{"key":"10.1016\/0196-6774(84)90045-2_BIB23","series-title":"An NP-hard graph drawing problem","author":"Eades","year":"1983"},{"key":"10.1016\/0196-6774(84)90045-2_BIB24","unstructured":"R. E. Erickson, C. L. Monma, and A. F. Veinott, Jr, Minimum-concave-cost network flows, Math. Oper. Res., to appear."},{"key":"10.1016\/0196-6774(84)90045-2_BIB25","article-title":"Application of 1.p. duality to problems involving independence and domination","author":"Farber","year":"1981"},{"key":"10.1016\/0196-6774(84)90045-2_BIB26","doi-asserted-by":"crossref","first-page":"134","DOI":"10.1016\/0167-6377(82)90015-3","article-title":"Independent domination in chordal graphs","volume":"1","author":"Farber","year":"1982","journal-title":"Operations Res. Lett."},{"key":"10.1016\/0196-6774(84)90045-2_BIB27","doi-asserted-by":"crossref","unstructured":"M. Farber, Domination, independent domination, and duality in strongly chordal graphs, Disc. Applied Math., to appear.","DOI":"10.1016\/0166-218X(84)90061-1"},{"key":"10.1016\/0196-6774(84)90045-2_BIB28","doi-asserted-by":"crossref","unstructured":"A. Frank, Disjoint paths in a rectilinear grid, Combinatorica, to appear.","DOI":"10.1007\/BF02579432"},{"key":"10.1016\/0196-6774(84)90045-2_BIB29","unstructured":"M. R. Garey and D. S. Johnson, unpublished result (1978) cited in [G & J]."},{"key":"10.1016\/0196-6774(84)90045-2_BIB30","article-title":"Optimal wiring with movable terminals","author":"Gopal","year":"1982"},{"key":"10.1016\/0196-6774(84)90045-2_BIB31","doi-asserted-by":"crossref","first-page":"529","DOI":"10.1137\/0211042","article-title":"The Hamiltonian circuit problem is polynomial for 4-connected planar graphs","volume":"11","author":"Gouyou-Beauchamps","year":"1982","journal-title":"SIAM J. Comput."},{"key":"10.1016\/0196-6774(84)90045-2_BIB32","article-title":"Solving NP-hard problems on graphs that are almost trees and an application to facility location problems","author":"Gurevich","year":"1982"},{"key":"10.1016\/0196-6774(84)90045-2_BIB33","article-title":"A linear algorithm for the domination number of a cactus","author":"Hedetniemi","year":"1983"},{"key":"10.1016\/0196-6774(84)90045-2_BIB34","first-page":"449","article-title":"A polynomial time algorithm to find a path cover of a reducible flow graph","volume":"E62","author":"Hirata","year":"1979","journal-title":"Trans. of the IECE of Japan"},{"key":"10.1016\/0196-6774(84)90045-2_BIB35","doi-asserted-by":"crossref","first-page":"96","DOI":"10.1016\/0167-6377(82)90005-0","article-title":"The distance-domination number of trees","volume":"1","author":"Hsu","year":"1982","journal-title":"Operations Res. Lett."},{"key":"10.1016\/0196-6774(84)90045-2_BIB36","doi-asserted-by":"crossref","first-page":"188","DOI":"10.1109\/TC.1982.1675974","article-title":"Deadlock-free systems for a bounded number of processes","author":"Ibaraki","year":"1982","journal-title":"IEEE Trans. Computers"},{"key":"10.1016\/0196-6774(84)90045-2_BIB37","doi-asserted-by":"crossref","first-page":"676","DOI":"10.1137\/0211056","article-title":"Hamilton paths in grid graphs","volume":"11","author":"Itai","year":"1982","journal-title":"SIAM J. Comput."},{"key":"10.1016\/0196-6774(84)90045-2_BIB38","series-title":"Proceedings 23rd Ann. Symp. on Foundations of Computer Science","first-page":"312","article-title":"An efficient approximation scheme for the one-dimensional bin-packing problem","author":"Karmarkar","year":"1982"},{"key":"10.1016\/0196-6774(84)90045-2_BIB39","article-title":"CHISEL: An extension to the programming language C for VLSI layout","author":"Karplus","year":"1982"},{"key":"10.1016\/0196-6774(84)90045-2_BIB40","article-title":"Decomposing polygons into simpler components","author":"Keil","year":"1983"},{"key":"10.1016\/0196-6774(84)90045-2_BIB41","article-title":"Dominating set in planar graphs","author":"Kikuno","year":"1979"},{"key":"10.1016\/0196-6774(84)90045-2_BIB42","series-title":"The NP-completeness of the dominating set problem in cubic planar graphs","author":"Kikuno","year":"1979"},{"key":"10.1016\/0196-6774(84)90045-2_BIB43","unstructured":"D. Kirkpatrick, private communication (1980)."},{"key":"10.1016\/0196-6774(84)90045-2_BIB44","series-title":"The NP-completeness of finding minimum area layouts for arbitrary VLSI circuits","author":"Kramer","year":"1982"},{"key":"10.1016\/0196-6774(84)90045-2_BIB45","article-title":"Domination and irredundance in split graphs","author":"Laskar","year":"1983"},{"key":"10.1016\/0196-6774(84)90045-2_BIB46","article-title":"On the algorithmic complexity of total domination","author":"Laskar","year":"1983"},{"key":"10.1016\/0196-6774(84)90045-2_BIB47","series-title":"Complexity of optimal deadlock recovery","author":"Leung","year":"1983"},{"key":"10.1016\/0196-6774(84)90045-2_BIB48","doi-asserted-by":"crossref","first-page":"671","DOI":"10.1109\/TC.1979.1675435","article-title":"On minimal cost recovery from system deadlock","volume":"C-28","author":"Leung","year":"1979","journal-title":"IEEE Trans. Computers"},{"key":"10.1016\/0196-6774(84)90045-2_BIB49","article-title":"Wire length minimization in a simple single-layer circuit","author":"Lin","year":"1983"},{"key":"10.1016\/0196-6774(84)90045-2_BIB50","series-title":"Minimum perimeter partitions of planar figures","author":"Lingas","year":"1982"},{"key":"10.1016\/0196-6774(84)90045-2_BIB51","series-title":"Automata, Languages, and Programming","first-page":"369","article-title":"The power of non-rectilinear holes","volume":"Vol. 140","author":"Lingas","year":"1982"},{"key":"10.1016\/0196-6774(84)90045-2_BIB52","article-title":"Advances in Minimum Weight Triangulation","author":"Lingas","year":"1983"},{"key":"10.1016\/0196-6774(84)90045-2_BIB53","series-title":"An NP-complete geometric problem related to three-layer channel routing","author":"Lipski","year":"1982"},{"key":"10.1016\/0196-6774(84)90045-2_BIB54","first-page":"193","article-title":"An algorithm for a merge recognition problem","volume":"4","author":"Mansfield","year":"1982"},{"key":"10.1016\/0196-6774(84)90045-2_BIB55","first-page":"119","article-title":"On the computational complexity of a merge recognition problem","volume":"5","author":"Mansfield","year":"1983"},{"key":"10.1016\/0196-6774(84)90045-2_BIB56","doi-asserted-by":"crossref","DOI":"10.21236\/ADA131387","article-title":"A combinatorial approach to some sparse matrix problems","author":"McCormick","year":"1983"},{"key":"10.1016\/0196-6774(84)90045-2_BIB57","unstructured":"Z. Miller and J. B. Orlin, Optimal grid embeddings of graphs, J. Algorithm, to appear."},{"key":"10.1016\/0196-6774(84)90045-2_BIB58","article-title":"The bandwidth-minization problem for caterpillars with hair length 3 is NP-complete","author":"Monien","year":"1983"},{"key":"10.1016\/0196-6774(84)90045-2_BIB59","first-page":"320","article-title":"Optimal two processor scheduling of tree precedence constrained tasks with two execution times","volume":"1","author":"Nakajima","year":"1981","journal-title":"Performance Evaluation"},{"key":"10.1016\/0196-6774(84)90045-2_BIB60","doi-asserted-by":"crossref","first-page":"261","DOI":"10.1016\/0020-0190(78)90012-1","article-title":"Optimum dominatoni in weighted trees","volume":"7","author":"Natarajan","year":"1978","journal-title":"Inform. Process. Lett."},{"key":"10.1016\/0196-6774(84)90045-2_BIB61","unstructured":"J. B. Orlin, private communication (1980)."},{"key":"10.1016\/0196-6774(84)90045-2_BIB62","article-title":"NP-completeness of total and connected domination, and irredundance for bipartite graphs","author":"Pfaff","year":"1983"},{"key":"10.1016\/0196-6774(84)90045-2_BIB63","series-title":"Proceedings 23rd Ann. Symp. on Foundations of Computer Science","first-page":"350","article-title":"Three layers are enough","author":"Preparata","year":"1982"},{"key":"10.1016\/0196-6774(84)90045-2_BIB64","doi-asserted-by":"crossref","first-page":"127","DOI":"10.1007\/BF00977745","article-title":"Minimum dominating cycles in outerplanar graphs","volume":"10","author":"Proskurowski","year":"1981","journal-title":"Internat. J. Comput. Information Sci."},{"key":"10.1016\/0196-6774(84)90045-2_BIB65","article-title":"Efficient vertex- and edge-coloring of outerplanar graphs","author":"Proskurowski","year":"1982"},{"key":"10.1016\/0196-6774(84)90045-2_BIB66","article-title":"A polynomial algorithm for the Steiner tree problem on terminal-planar graphs","author":"Provan","year":"1983"},{"key":"10.1016\/0196-6774(84)90045-2_BIB67","series-title":"Manhattan and rectilinear wiring","author":"Raghavan","year":"1982"},{"key":"10.1016\/0196-6774(84)90045-2_BIB68","series-title":"Proceedings 11th Ann. ACM Symp. on Principles of Programming Languages","article-title":"The global storage needs of a subcompaction","author":"Raoult","year":"1984"},{"key":"10.1016\/0196-6774(84)90045-2_BIB69","article-title":"On a class of graphs having at most one Hamiltonian cycle","author":"Richey","year":"1982"},{"key":"10.1016\/0196-6774(84)90045-2_BIB70","article-title":"Exponential time decision problems relating to KO-like transitions rules","author":"Robson","year":"1982"},{"key":"10.1016\/0196-6774(84)90045-2_BIB71","article-title":"The complexity of Go","author":"Robson","year":"1982"},{"key":"10.1016\/0196-6774(84)90045-2_BIB72","unstructured":"J. M. Robson, private communication (1983)."},{"key":"10.1016\/0196-6774(84)90045-2_BIB73","series-title":"Proc. 7th Conf. on Graph Theoretic Concepts in Computer Science","first-page":"99","article-title":"Bus routing problems in acyclic networks","author":"R\u00f6ck","year":"1982"},{"key":"10.1016\/0196-6774(84)90045-2_BIB74","article-title":"Two papers on graph embedding problems","author":"Saxe","year":"1980"},{"key":"10.1016\/0196-6774(84)90045-2_BIB75","unstructured":"D. Seese, private communication (1983)."},{"key":"10.1016\/0196-6774(84)90045-2_BIB76","doi-asserted-by":"crossref","first-page":"226","DOI":"10.1137\/0204020","article-title":"Complete register allocation problems","volume":"4","author":"Sethi","year":"1975","journal-title":"SIAM J. Comput."},{"key":"10.1016\/0196-6774(84)90045-2_BIB77","doi-asserted-by":"crossref","first-page":"69","DOI":"10.1016\/0304-3975(82)90015-9","article-title":"Pebble games for studying storage sharing","volume":"19","author":"Sethi","year":"1982","journal-title":"Theor. Comput. Sci."},{"key":"10.1016\/0196-6774(84)90045-2_BIB78","doi-asserted-by":"crossref","first-page":"446","DOI":"10.1145\/321958.321964","article-title":"R-domination in graphs","volume":"23","author":"Slater","year":"1976","journal-title":"J. Assoc. Comput. Mach."},{"key":"10.1016\/0196-6774(84)90045-2_BIB79","unstructured":"N. J. A. Sloane, private communication (1983)."},{"key":"10.1016\/0196-6774(84)90045-2_BIB80","article-title":"On the complexity of concurrency control by locking in distributed database systems","author":"Soisalon-Soininen","year":"1983"},{"key":"10.1016\/0196-6774(84)90045-2_BIB81","first-page":"1382","article-title":"Approximate algorithms for the edge-coloring of graphs","author":"Terada","year":"1982","journal-title":"Trans. of the IECE of Japan"},{"key":"10.1016\/0196-6774(84)90045-2_BIB82","series-title":"Proceedings 20th Ann. Allerton Conf. on Communication, Control, and Computing","first-page":"1008","article-title":"Realizing fault-tolerant binary trees in VLSI","author":"Varman","year":"1982"},{"key":"10.1016\/0196-6774(84)90045-2_BIB83","first-page":"9","article-title":"Critical graphs with a given chromatic class","volume":"5","author":"Vizing","year":"1965","journal-title":"Diskret. Analiz."},{"key":"10.1016\/0196-6774(84)90045-2_BIB84","article-title":"On the complexity of iterated shuffle","author":"Warmuth","year":"1981"},{"key":"10.1016\/0196-6774(84)90045-2_BIB85","series-title":"SIGMOD 83 Proceedings","first-page":"6","article-title":"On merging partitioned databases","author":"Wright","year":"1983"},{"key":"10.1016\/0196-6774(84)90045-2_BIB86","series-title":"Proceedings 24th Ann. Symp. on Foundations of Computer Science","first-page":"274","article-title":"A polynomial algorithm for min cut linear arrangement of trees","author":"Yannakakis","year":"1983"}],"container-title":["Journal of Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:0196677484900452?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:0196677484900452?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2019,1,29]],"date-time":"2019-01-29T01:50:41Z","timestamp":1548726641000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/0196677484900452"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1984,3]]},"references-count":86,"journal-issue":{"issue":"1","published-print":{"date-parts":[[1984,3]]}},"alternative-id":["0196677484900452"],"URL":"https:\/\/doi.org\/10.1016\/0196-6774(84)90045-2","relation":{},"ISSN":["0196-6774"],"issn-type":[{"value":"0196-6774","type":"print"}],"subject":[],"published":{"date-parts":[[1984,3]]}}}