{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:12:26Z","timestamp":1759637546546},"reference-count":50,"publisher":"Elsevier BV","issue":"1","license":[{"start":{"date-parts":[[1985,3,1]],"date-time":"1985-03-01T00:00:00Z","timestamp":478483200000},"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":[[1985,3]]},"DOI":"10.1016\/0196-6774(85)90025-2","type":"journal-article","created":{"date-parts":[[2005,2,10]],"date-time":"2005-02-10T03:44:36Z","timestamp":1108007076000},"page":"145-159","source":"Crossref","is-referenced-by-count":23,"title":["The NP-completeness column: An ongoing guide"],"prefix":"10.1016","volume":"6","author":[{"given":"David S","family":"Johnson","sequence":"first","affiliation":[]}],"member":"78","reference":[{"key":"10.1016\/0196-6774(85)90025-2_BIB1","doi-asserted-by":"crossref","first-page":"315","DOI":"10.1137\/0213022","article-title":"Constrained optimum communication trees and sensitivity analysis","volume":"13","author":"Agarwal","year":"1984","journal-title":"SIAM J. Comput."},{"key":"10.1016\/0196-6774(85)90025-2_BIB2","doi-asserted-by":"crossref","first-page":"493","DOI":"10.1287\/opre.32.3.493","article-title":"An O (|E|) time algorithm for computing the reliability of a class of directed networks","volume":"32","author":"Agrawal","year":"1984","journal-title":"Operations Res."},{"key":"10.1016\/0196-6774(85)90025-2_BIB3","series-title":"Proceedings 25th Ann. Symp. on Foundations of Computer Science","first-page":"320","article-title":"Eigenvalues, expanders and superconcentrators","author":"Alon","year":"1984"},{"key":"10.1016\/0196-6774(85)90025-2_BIB4","doi-asserted-by":"crossref","first-page":"253","DOI":"10.1002\/net.3230130210","article-title":"Calculating bounds on reachability and connectedness in stochastic networks","volume":"13","author":"Ball","year":"1983","journal-title":"Networks"},{"key":"10.1016\/0196-6774(85)90025-2_BIB5","doi-asserted-by":"crossref","first-page":"164","DOI":"10.1016\/0020-0190(81)90050-8","article-title":"The complexity of testing whether a graph is a superconcentrator","volume":"13","author":"Blum","year":"1981","journal-title":"Inform. Process. Lett."},{"key":"10.1016\/0196-6774(85)90025-2_BIB6","doi-asserted-by":"crossref","first-page":"473","DOI":"10.1137\/0603048","article-title":"The bounded path tree problem","volume":"3","author":"Camerini","year":"1982","journal-title":"SIAM J. Algebraic and Discrete Methods"},{"key":"10.1016\/0196-6774(85)90025-2_BIB7","series-title":"Proceedings 17th Ann. Allerton Conf. on Communication, Control, and Computing","first-page":"969","article-title":"On the complexity of Steiner-like problems","author":"Camerini","year":"1979"},{"key":"10.1016\/0196-6774(85)90025-2_BIB8","doi-asserted-by":"crossref","first-page":"346","DOI":"10.1016\/0377-2217(80)90164-2","article-title":"Complexity of spanning tree problems: Part I","volume":"5","author":"Camerini","year":"1980","journal-title":"European J. Op. Res."},{"key":"10.1016\/0196-6774(85)90025-2_BIB9","doi-asserted-by":"crossref","first-page":"39","DOI":"10.1016\/0166-218X(83)90014-8","article-title":"On the complexity of finding multiconstrained spanning trees","volume":"5","author":"Camerini","year":"1983","journal-title":"Disc. Applied Math."},{"key":"10.1016\/0196-6774(85)90025-2_BIB10","series-title":"Proc. Colloq. on the Theory of Algorithms, P\u00e9cs 1984","article-title":"The complexity of weighted multiconstrained spanning tree problems","author":"Camerini","year":"1984"},{"key":"10.1016\/0196-6774(85)90025-2_BIB11","article-title":"Unlabelled partition systems: Optimization and complexity","author":"Camerini","year":"1983"},{"key":"10.1016\/0196-6774(85)90025-2_BIB12","doi-asserted-by":"crossref","first-page":"117","DOI":"10.1016\/0166-218X(84)90013-1","article-title":"Polynomial testing of the query \u2018Is ab >\/ cd?\u2019 with application to finding a minimal cost reliability ratio spanning tree","volume":"9","author":"Chandrasekaran","year":"1984","journal-title":"Disc. Applied Math."},{"key":"10.1016\/0196-6774(85)90025-2_BIB13","doi-asserted-by":"crossref","first-page":"1765","DOI":"10.1002\/j.1538-7305.1979.tb02972.x","article-title":"On concentrators, superconcentrators, generalizers, and nonblocking networks","volume":"58","author":"Chung","year":"1979","journal-title":"Bell Syst. Tech. J."},{"key":"10.1016\/0196-6774(85)90025-2_BIB14","doi-asserted-by":"crossref","first-page":"857","DOI":"10.1109\/TC.1984.1676504","article-title":"Large graphs with given degree and diameter \u2014 Part I","volume":"C-33","author":"Delorme","year":"1984","journal-title":"IEEE Trans. Computers"},{"key":"10.1016\/0196-6774(85)90025-2_BIB15","doi-asserted-by":"crossref","first-page":"26","DOI":"10.1145\/355984.355988","article-title":"Algorithms for generating fundamental cycles in a graph","volume":"8","author":"Deo","year":"1982","journal-title":"ACM Trans. Math. Software"},{"key":"10.1016\/0196-6774(85)90025-2_BIB16","doi-asserted-by":"crossref","first-page":"70","DOI":"10.1137\/0601010","article-title":"Rectilinear Steiner trees in rectangle trees","volume":"1","author":"Farley","year":"1980","journal-title":"SIAM J. Algebraic and Discrete Methods"},{"key":"10.1016\/0196-6774(85)90025-2_BIB17","doi-asserted-by":"crossref","first-page":"555","DOI":"10.1109\/TC.1982.1676041","article-title":"The complexity of fault detection problems for combinational logic circuits","volume":"C-31","author":"Fujiwara","year":"1982","journal-title":"IEEE Trans. Computers"},{"key":"10.1016\/0196-6774(85)90025-2_BIB18","doi-asserted-by":"crossref","first-page":"407","DOI":"10.1016\/0022-0000(81)90040-4","article-title":"Explicit construction of linear-sized superconcentrators","volume":"22","author":"Gabber","year":"1981","journal-title":"J. Comput. System Sci."},{"key":"10.1016\/0196-6774(85)90025-2_BIB19","series-title":"Proceedings 25th Ann. Symp. on Foundations of Computer Science","first-page":"347","article-title":"Efficient implementation of graph algorithms using contraction","author":"Gabow","year":"1984"},{"key":"10.1016\/0196-6774(85)90025-2_BIB20","doi-asserted-by":"crossref","first-page":"377","DOI":"10.1002\/net.3230130306","article-title":"An algorithm for constructing edge-trees from hypergraphs","volume":"13","author":"Gavril","year":"1983","journal-title":"Networks"},{"key":"10.1016\/0196-6774(85)90025-2_BIB21","doi-asserted-by":"crossref","first-page":"169","DOI":"10.1007\/BF02579273","article-title":"The ellipsoid method and its consequences in combinatorial optimization","volume":"1","author":"Gr\u00f6tschel","year":"1981","journal-title":"Combinatorica"},{"key":"10.1016\/0196-6774(85)90025-2_BIB22","series-title":"Computing rooted communication reliability is #P-complete","author":"Hagstrom","year":"1981"},{"key":"10.1016\/0196-6774(85)90025-2_BIB23","article-title":"Generation of minimal test sets for system diagnosis","author":"Ibaraki","year":"1979"},{"key":"10.1016\/0196-6774(85)90025-2_BIB24","doi-asserted-by":"crossref","first-page":"182","DOI":"10.1109\/TC.1981.1675754","article-title":"On minimal test sets for locating single link failures in networks","volume":"C-30","author":"Ibaraki","year":"1981","journal-title":"IEEE Trans. Computers"},{"key":"10.1016\/0196-6774(85)90025-2_BIB25","series-title":"Studies on Graphs and Discrete Programming","first-page":"215","article-title":"Minimal test set for diagnosing a tree system","author":"Ibaraki","year":"1981"},{"key":"10.1016\/0196-6774(85)90025-2_BIB26","article-title":"On the Complexity of Evaluating Multivariate Polynomials","author":"Jerrum","year":"1981"},{"key":"10.1016\/0196-6774(85)90025-2_BIB27","series-title":"Hypergraph planarity and the complexity of drawing Venn diagrams, manuscript","author":"Johnson","year":"1984"},{"key":"10.1016\/0196-6774(85)90025-2_BIB28","doi-asserted-by":"crossref","first-page":"750","DOI":"10.1109\/TC.1984.5009364","article-title":"On the complexity of estimating the size of a test set","volume":"C-33","author":"Krishnamurthy","year":"1984","journal-title":"IEEE Trans. Computers"},{"key":"10.1016\/0196-6774(85)90025-2_BIB29","unstructured":"T. Lengauer and S. N\u00e4her, \u201cDelay-independent switch level simulation of digital MOS circuits,\u201d Report No. 03\/1984, Fachbereich 10, Universit\u00e4t des Saarlandes, Saarbr\u00fccken, West Germany."},{"key":"10.1016\/0196-6774(85)90025-2_BIB30","doi-asserted-by":"crossref","first-page":"105","DOI":"10.1016\/0167-6377(82)90007-4","article-title":"On the complexity of the one-terminal network design problem","volume":"1","author":"Megiddo","year":"1982","journal-title":"Operations Res. Lett."},{"key":"10.1016\/0196-6774(85)90025-2_BIB31","series-title":"Combinatorial Optimization: Algorithms and Complexity","author":"Papadimitriou","year":"1982"},{"key":"10.1016\/0196-6774(85)90025-2_BIB32","doi-asserted-by":"crossref","first-page":"367","DOI":"10.1016\/0196-6774(84)90017-8","article-title":"Optimum split trees","volume":"5","author":"Perl","year":"1984","journal-title":"J. Algorithms"},{"key":"10.1016\/0196-6774(85)90025-2_BIB33","doi-asserted-by":"crossref","first-page":"512","DOI":"10.1137\/0604050","article-title":"Efficient optimization of monotonic functions on trees","volume":"4","author":"Perl","year":"1983","journal-title":"SIAM J. Algebraic and Discrete Methods"},{"key":"10.1016\/0196-6774(85)90025-2_BIB34","doi-asserted-by":"crossref","first-page":"77","DOI":"10.1002\/net.3230110110","article-title":"The complexity of designing a network with minimum diameter","volume":"11","author":"Plesn\u00edk","year":"1981","journal-title":"Networks"},{"key":"10.1016\/0196-6774(85)90025-2_BIB35","first-page":"379","article-title":"Complexity of decomposing graphs into factors with given diameters or radii","volume":"32","author":"Plesn\u00edk","year":"1982","journal-title":"Math. Slovaca"},{"key":"10.1016\/0196-6774(85)90025-2_BIB36","first-page":"215","article-title":"On the complexity of finding degree constrained subgraphs","volume":"40","author":"Plesn\u00edk","year":"1982","journal-title":"Acta Math. Universitatis Comenianae"},{"key":"10.1016\/0196-6774(85)90025-2_BIB37","doi-asserted-by":"crossref","DOI":"10.21236\/ADA150759","article-title":"The complexity of reliability computations in planar and acyclic graphs","author":"Provan","year":"1984"},{"key":"10.1016\/0196-6774(85)90025-2_BIB38","doi-asserted-by":"crossref","first-page":"777","DOI":"10.1137\/0212053","article-title":"The complexity of counting cuts and computing the probability that a graph is connected","volume":"12","author":"Provan","year":"1983","journal-title":"SIAM J. Comput."},{"key":"10.1016\/0196-6774(85)90025-2_BIB39","doi-asserted-by":"crossref","first-page":"516","DOI":"10.1287\/opre.32.3.516","article-title":"Computing network reliability in time polynomial in the number of cuts","volume":"32","author":"Provan","year":"1984","journal-title":"Operations Res."},{"key":"10.1016\/0196-6774(85)90025-2_BIB40","series-title":"Proc. IEEE International Conference on Computer Design: VLSI in Computers","first-page":"345","article-title":"A linear-time algorithm for race detection in transistor switch-level circuits","author":"Ramachandran","year":"1983"},{"key":"10.1016\/0196-6774(85)90025-2_BIB41","article-title":"A linear-time algorithm for switch-level simulation with race detection in a class of MOS VLSI circuits","author":"Ramachandran","year":"1984"},{"key":"10.1016\/0196-6774(85)90025-2_BIB42","doi-asserted-by":"crossref","DOI":"10.21236\/ADA116276","article-title":"Polygon-to-chain reductions and network reliability","author":"Satyanarayana","year":"1982"},{"key":"10.1016\/0196-6774(85)90025-2_BIB43","doi-asserted-by":"crossref","first-page":"186","DOI":"10.1016\/0020-0190(82)90103-X","article-title":"A linear algorithm for the number of degree constrained subforests of a tree","volume":"15","author":"Slater","year":"1982","journal-title":"Inform. Process. Lett."},{"key":"10.1016\/0196-6774(85)90025-2_BIB44","doi-asserted-by":"crossref","first-page":"37","DOI":"10.1002\/net.3230140104","article-title":"On the computational complexity of the minimum-dummy-activities problem in a PERT network","volume":"14","author":"Syslo","year":"1984","journal-title":"Networks"},{"key":"10.1016\/0196-6774(85)90025-2_BIB45","doi-asserted-by":"crossref","first-page":"47","DOI":"10.1007\/BF00289139","article-title":"Optimal multiway search trees for variable size keys","volume":"21","author":"Szwarcfiter","year":"1984","journal-title":"Acta Inform"},{"key":"10.1016\/0196-6774(85)90025-2_BIB46","series-title":"Proceedings 7th Ann. ACM Symp. on Theory of Computing","first-page":"45","article-title":"On nonlinear lower bounds in computational complexity","author":"Valiant","year":"1975"},{"key":"10.1016\/0196-6774(85)90025-2_BIB47","doi-asserted-by":"crossref","first-page":"278","DOI":"10.1016\/S0022-0000(76)80041-4","article-title":"Graph-theoretic properties in computational complexity","volume":"13","author":"Valiant","year":"1976","journal-title":"J. Comput. System Sci."},{"key":"10.1016\/0196-6774(85)90025-2_BIB48","doi-asserted-by":"crossref","first-page":"410","DOI":"10.1137\/0208032","article-title":"The complexity of enumeration and reliability problems","volume":"8","author":"Valiant","year":"1979","journal-title":"SIAM J. Comput."},{"key":"10.1016\/0196-6774(85)90025-2_BIB49","unstructured":"A. Vergis, manuscript (1983)."},{"key":"10.1016\/0196-6774(85)90025-2_BIB50","doi-asserted-by":"crossref","first-page":"439","DOI":"10.1002\/net.3230120408","article-title":"Polynomial algorithms for estimating network reliability","volume":"12","author":"Zemel","year":"1982","journal-title":"Networks"}],"container-title":["Journal of Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:0196677485900252?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:0196677485900252?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:26:32Z","timestamp":1548725192000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/0196677485900252"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1985,3]]},"references-count":50,"journal-issue":{"issue":"1","published-print":{"date-parts":[[1985,3]]}},"alternative-id":["0196677485900252"],"URL":"https:\/\/doi.org\/10.1016\/0196-6774(85)90025-2","relation":{},"ISSN":["0196-6774"],"issn-type":[{"value":"0196-6774","type":"print"}],"subject":[],"published":{"date-parts":[[1985,3]]}}}