The DOI matches its Crossref record.
Complexity of Computer Computations
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cited by
New directions in cryptography
Diffie, W., & Hellman, M. (1976) · IEEE Transactions on Information Theory · doi:10.1109/tit.1976.1055638 · Cited by 14,713
Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey
Graham, R. L., Lawler, E. L., Lenstra, J. K., & Kan, A. H. G. R. (1979) · Annals of Discrete Mathematics · doi:10.1016/s0167-5060(08)70356-x · Cited by 5,854
Molecular Computation of Solutions to Combinatorial Problems
Adleman, L. M. (1994) · Science · doi:10.1126/science.7973651 · Cited by 4,474
Routing of multipoint connections
Waxman, B. M. (1988) · IEEE Journal on Selected Areas in Communications · doi:10.1109/49.12889 · Cited by 2,885
The complexity of computing the permanent
Valiant, L. G. (1979) · Theoretical Computer Science · doi:10.1016/0304-3975(79)90044-6 · Cited by 2,705
Ising formulations of many NP problems
Lucas, A. (2014) · Frontiers in Physics · doi:10.3389/fphy.2014.00005 · Cited by 2,512
Approximation algorithms for combinatorial problems
Johnson, D. S. (1974) · Journal of Computer and System Sciences · doi:10.1016/s0022-0000(74)80044-9 · Cited by 2,197
Complexity of Machine Scheduling Problems
Lenstra, J. K., Rinnooy Kan, A. H. G., & Brucker, P. (1977) · Annals of Discrete Mathematics · doi:10.1016/s0167-5060(08)70743-x · Cited by 2,197
Some simplified NP-complete graph problems
Garey, M. R., Johnson, D. S., & Stockmeyer, L. (1976) · Theoretical Computer Science · doi:10.1016/0304-3975(76)90059-1 · Cited by 2,059
Detecting community structure in networks
Newman, M. E. J. (2004) · The European Physical Journal B - Condensed Matter · doi:10.1140/epjb/e2004-00124-y · Cited by 2,028
Clustering to minimize the maximum intercluster distance
Gonzalez, T. F. (1985) · Theoretical Computer Science · doi:10.1016/0304-3975(85)90224-5 · Cited by 1,717
EXPERT SYSTEMS WITH APPLICATIONS
(2005) · Expert Systems with Applications · doi:10.1016/j.eswa.2004.10.010 · Cited by 1,656
Optimization, approximation, and complexity classes
Papadimitriou, C. H., & Yannakakis, M. (1991) · Journal of Computer and System Sciences · doi:10.1016/0022-0000(91)90023-x · Cited by 1,653
Albash, T., & Lidar, D. A. (2018) · Reviews of Modern Physics · doi:10.1103/revmodphys.90.015002 · Cited by 1,546
Clark, B. N., Colbourn, C. J., & Johnson, D. S. (1990) · Discrete Mathematics · doi:10.1016/0012-365x(90)90358-o · Cited by 1,429
On the computational complexity of Ising spin glass models
Barahona, F. (1982) · Journal of Physics A: Mathematical and General · doi:10.1088/0305-4470/15/10/028 · Cited by 1,306
Stockmeyer, L. J. (1976) · Theoretical Computer Science · doi:10.1016/0304-3975(76)90061-x · Cited by 1,293
Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems
Arora, S. (1998) · Journal of the ACM · doi:10.1145/290179.290180 · Cited by 1,137
Hopcroft, J., & Tarjan, R. (1974) · Journal of the ACM · doi:10.1145/321850.321852 · Cited by 1,081
Computationally Manageable Combinational Auctions
Rothkopf, M. H., Pekeč, A., & Harstad, R. M. (1998) · Management Science · doi:10.1287/mnsc.44.8.1131 · Cited by 1,024
Linear-time algorithms for testing the satisfiability of propositional horn formulae
Dowling, W. F., & Gallier, J. H. (1984) · The Journal of Logic Programming · doi:10.1016/0743-1066(84)90014-1 · Cited by 1,013
The Analysis of Natural Microbial Populations by Ribosomal RNA Sequences
Pace, N. R., Stahl, D. A., Lane, D. J., & Olsen, G. J. (1986) · Advances in Microbial Ecology · doi:10.1007/978-1-4757-0611-6_1 · Cited by 919
Routing and scheduling of vehicles and crews
Raff, S. (1983) · Computers & Operations Research · doi:10.1016/0305-0548(83)90030-8 · Cited by 867
Boros, E., & Hammer, P. L. (2002) · Discrete Applied Mathematics · doi:10.1016/s0166-218x(01)00341-9 · Cited by 827
The Euclidean travelling salesman problem is NP-complete
Papadimitriou, C. H. (1977) · Theoretical Computer Science · doi:10.1016/0304-3975(77)90012-3 · Cited by 776
OptiType: precision HLA typing from next-generation sequencing data
Szolek, A., Schubert, B., Mohr, C., Sturm, M., Feldhahn, M., & Kohlbacher, O. (2014) · Bioinformatics · doi:10.1093/bioinformatics/btu548 · Cited by 769
Chapter 9 Sequencing and scheduling: Algorithms and complexity
Lawler, E. L., Lenstra, J. K., Rinnooy Kan, A. H. G., & Shmoys, D. B. (1993) · Handbooks in Operations Research and Management Science · doi:10.1016/s0927-0507(05)80189-6 · Cited by 761
In-network aggregation techniques for wireless sensor networks: a survey
Fasolo, E., Rossi, M., Widmer, J., & Zorzi, M. (2007) · IEEE Wireless Communications · doi:10.1109/mwc.2007.358967 · Cited by 734
A survey of computational complexity results in systems and control
Blondel, V. D., & Tsitsiklis, J. N. (2000) · Automatica · doi:10.1016/s0005-1098(00)00050-9 · Cited by 732
Riemann's hypothesis and tests for primality
Miller, G. L. (1976) · Journal of Computer and System Sciences · doi:10.1016/s0022-0000(76)80043-8 · Cited by 709
Chaotic simulated annealing by a neural network model with transient chaos
Chen, L., & Aihara, K. (1995) · Neural Networks · doi:10.1016/0893-6080(95)00033-v · Cited by 661
Control principles of complex systems
Liu, Y.-Y., & Barabási, A.-L. (2016) · Reviews of Modern Physics · doi:10.1103/revmodphys.88.035006 · Cited by 654
Edmonds polytopes and a hierarchy of combinatorial problems
Chvátal, V. (1973) · Discrete Mathematics · doi:10.1016/0012-365x(73)90167-2 · Cited by 624
Fast probabilistic algorithms for hamiltonian circuits and matchings
Angluin, D., & Valiant, L. G. (1979) · Journal of Computer and System Sciences · doi:10.1016/0022-0000(79)90045-x · Cited by 570
A Catalog of Complexity Classes
JOHNSON, D. S. (1990) · Algorithms and Complexity · doi:10.1016/b978-0-444-88071-0.50007-2 · Cited by 556
The simple plant location problem: Survey and synthesis
Krarup, J., & Pruzan, P. M. (1983) · European Journal of Operational Research · doi:10.1016/0377-2217(83)90181-9 · Cited by 544
Fast algorithms for bin packing
Johnson, D. S. (1974) · Journal of Computer and System Sciences · doi:10.1016/s0022-0000(74)80026-7 · Cited by 540
Shepard, R. N., & Arabie, P. (1979) · Psychological Review · doi:10.1037//0033-295x.86.2.87 · Cited by 476
Algorithms for Knapsack Problems
Martello, S., & Toth, P. (1987) · North-Holland Mathematics Studies · doi:10.1016/s0304-0208(08)73237-7 · Cited by 466
A Gentle Introduction to Memetic Algorithms
Moscato, P., & Cotta, C. (2006) · International Series in Operations Research & Management Science · doi:10.1007/0-306-48056-5_5 · Cited by 457
Drift analysis and average time complexity of evolutionary algorithms
He, J., & Yao, X. (2001) · Artificial Intelligence · doi:10.1016/s0004-3702(01)00058-3 · Cited by 457
Aggregation of Inequalities in Integer Programming
Chvátal, V., & Hammer, P. L. (1977) · Annals of Discrete Mathematics · doi:10.1016/s0167-5060(08)70731-3 · Cited by 448
The complexity of optimization problems
Krentel, M. W. (1988) · Journal of Computer and System Sciences · doi:10.1016/0022-0000(88)90039-6 · Cited by 441
Approximation Algorithms for Bin-Packing — An Updated Survey
Coffman, E. G., Garey, M. R., & Johnson, D. S. (1984) · CISM International Centre for Mechanical Sciences · doi:10.1007/978-3-7091-4338-4_3 · Cited by 433
A linear-time approximation algorithm for the weighted vertex cover problem
Bar-Yehuda, R., & Even, S. (1981) · Journal of Algorithms · doi:10.1016/0196-6774(81)90020-1 · Cited by 430
Some applications of Laplace eigenvalues of graphs
Mohar, B. (1997) · Graph Symmetry · doi:10.1007/978-94-015-8937-6_6 · Cited by 422
Complete sets and the polynomial-time hierarchy
Wrathall, C. (1976) · Theoretical Computer Science · doi:10.1016/0304-3975(76)90062-1 · Cited by 394
Coherent Ising machine based on degenerate optical parametric oscillators
Wang, Z., Marandi, A., Wen, K., Byer, R. L., & Yamamoto, Y. (2013) · Physical Review A · doi:10.1103/physreva.88.063853 · Cited by 391
Burkard, R. E. (1984) · European Journal of Operational Research · doi:10.1016/0377-2217(84)90093-6 · Cited by 378
The Hardness of Approximate Optima in Lattices, Codes, and Systems of Linear Equations
Arora, S., Babai, L., Stern, J., & Sweedyk, Z. (1997) · Journal of Computer and System Sciences · doi:10.1006/jcss.1997.1472 · Cited by 344
Linear Assignment Problems and Extensions
Burkard, R. E., & Çela, E. (1999) · Handbook of Combinatorial Optimization · doi:10.1007/978-1-4757-3023-4_2 · Cited by 330
Algorithms for Computing Minimal Unsatisfiable Subsets of Constraints
Liffiton, M. H., & Sakallah, K. A. (2008) · Journal of Automated Reasoning · doi:10.1007/s10817-007-9084-z · Cited by 329
A review on algorithms for maximum clique problems
Wu, Q., & Hao, J.-K. (2015) · European Journal of Operational Research · doi:10.1016/j.ejor.2014.09.064 · Cited by 314
EnaCloud: An Energy-Saving Application Live Placement Approach for Cloud Computing Environments
Li, B., Li, J., Huai, J., Wo, T., Li, Q., & Zhong, L. (2009) · 2009 IEEE International Conference on Cloud Computing · doi:10.1109/cloud.2009.72 · Cited by 313
A Review of Methodological Approaches for the Design and Optimization of Wind Farms
Herbert-Acero, J., Probst, O., Réthoré, P.-E., Larsen, G., & Castillo-Villar, K. (2014) · Energies · doi:10.3390/en7116930 · Cited by 311
The complexity of facets (and some facets of complexity)
Papadimitriou, C. H., & Yannakakis, M. (1984) · Journal of Computer and System Sciences · doi:10.1016/0022-0000(84)90068-0 · Cited by 307
Phase transitions in the coloring of random graphs
Zdeborová, L., & Krząkała, F. (2007) · Physical Review E · doi:10.1103/physreve.76.031131 · Cited by 306
Linear-space best-first search
Korf, R. E. (1993) · Artificial Intelligence · doi:10.1016/0004-3702(93)90045-d · Cited by 305
A systematic survey of computer-aided diagnosis in medicine: Past and present developments
Yanase, J., & Triantaphyllou, E. (2019) · Expert Systems with Applications · doi:10.1016/j.eswa.2019.112821 · Cited by 303
Sparse complete sets for NP: Solution of a conjecture of Berman and Hartmanis
Mahaney, S. R. (1982) · Journal of Computer and System Sciences · doi:10.1016/0022-0000(82)90002-2 · Cited by 299
Computational Complexity of Discrete Optimization Problems
Lenstra, J. K., & Rinnooy Kan, A. H. G. (1979) · Annals of Discrete Mathematics · doi:10.1016/s0167-5060(08)70821-5 · Cited by 292
A simulated annealing heuristic for the capacitated location routing problem
Yu, V. F., Lin, S.-W., Lee, W., & Ting, C.-J. (2010) · Computers & Industrial Engineering · doi:10.1016/j.cie.2009.10.007 · Cited by 287
Complete problems for deterministic polynomial time
Jones, N. D., & Laaser, W. T. (1976) · Theoretical Computer Science · doi:10.1016/0304-3975(76)90068-2 · Cited by 279
Relative complexity of checking and evaluating
Valiant, L. G. (1976) · Information Processing Letters · doi:10.1016/0020-0190(76)90097-1 · Cited by 277
Contentment in graph theory: Covering graphs with cliques
Orlin, J. (1977) · Indagationes Mathematicae (Proceedings) · doi:10.1016/1385-7258(77)90055-5 · Cited by 275
Solving propositional satisfiability problems
Jeroslow, R. G., & Wang, J. (1990) · Annals of Mathematics and Artificial Intelligence · doi:10.1007/bf01531077 · Cited by 270
An Experimental Study of the Coloring Problem on Human Subject Networks
Kearns, M., Suri, S., & Montfort, N. (2006) · Science · doi:10.1126/science.1127207 · Cited by 269
Measurement optimization in the variational quantum eigensolver using a minimum clique cover
Verteletskyi, V., Yen, T.-C., & Izmaylov, A. F. (2020) · The Journal of Chemical Physics · doi:10.1063/1.5141458 · Cited by 269
Structure preserving reductions among convex optimization problems
Ausiello, G., D'Atri, A., & Protasi, M. (1980) · Journal of Computer and System Sciences · doi:10.1016/0022-0000(80)90046-x · Cited by 264
A class of algorithms which require nonlinear time to maintain disjoint sets
Tarjan, R. E. (1979) · Journal of Computer and System Sciences · doi:10.1016/0022-0000(79)90042-4 · Cited by 263
Substitution Decomposition for Discrete Structures and Connections with Combinatorial Optimization
Möhring, R. H., & Radermacher, F. J. (1984) · North-Holland Mathematics Studies · doi:10.1016/s0304-0208(08)72966-9 · Cited by 258
Computability: An introduction to recursive function theory
Cutland, N. (1980) · doi:10.1017/cbo9781139171496 · Cited by 206
On-line bin packing in linear time
Ramanan, P., Brown, D. J., Lee, C. C., & Lee, D. T. (1989) · Journal of Algorithms · doi:10.1016/0196-6774(89)90031-x · Cited by 127
Minimum energy requirements of information transfer and computing
Bremermann, H. J. (1982) · International Journal of Theoretical Physics · doi:10.1007/bf01857726 · Cited by 63
A study of the performance of classical minimizers in the Quantum Approximate Optimization Algorithm
Fernández-Pendás, M., Combarro, E. F., Vallecorsa, S., Ranilla, J., & Rúa, I. F. (2022) · Journal of Computational and Applied Mathematics · doi:10.1016/j.cam.2021.113388 · Cited by 52
Unsupervised tip-mining from customer reviews
Zhu, D., Lappas, T., & Zhang, J. (2018) · Decision Support Systems · doi:10.1016/j.dss.2018.01.011 · Cited by 32
Approximating the quantum approximate optimization algorithm with digital-analog interactions
Headley, D., Müller, T., Martin, A., Solano, E., Sanz, M., & Wilhelm, F. K. (2020) · arXiv · doi:10.48550/arxiv.2002.12215 · Cited by 21
Online perceptual learning and natural language acquisition for autonomous robots
Alomari, M., Li, F., Hogg, D. C., & Cohn, A. G. (2022) · Artificial Intelligence · doi:10.1016/j.artint.2021.103637 · Cited by 17
A Genetic Algorithm for Solving the Euclidean Non-Uniform Steiner Tree Problem
Frommer, I., & Golden, B. (2007) · Operations Research/Computer Science Interfaces Series · doi:10.1007/978-0-387-48793-9_3 · Cited by 3
Power and Limitations of Linear Programming Decoder for Quantum LDPC Codes
Gu, S., & Soleimanifar, M. (2025) · arXiv · doi:10.48550/arxiv.2508.04769 · Cited by 2
Metadata
- Venue
- Springer eBooks
- Publisher
- Springer US
- Published
- 1972
- OpenAlex
- W2066356146
- Cited by
- 2,781
- References
- 0
- FWCI
- 15.69
- Type
- book
- Language
- en
- Open access
- closed
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.