Most cited papers in Complexity and Algorithms in Graphs
What are the most cited papers in Complexity and Algorithms in Graphs?
The most cited paper in Complexity and Algorithms in Graphs is "Public-Key Cryptosystems Based on Composite Degree Residuosity Classes" (Pascal Paillier, 2007), with 7,322 citations. Next come "Identity-Based Encryption from the Weil Pairing" (7,095) and "Fully homomorphic encryption using ideal lattices" (6,742).
Showing 50 of 97 papers. Every paper with more than 1,006 citations is listed.
| # | Paper | ||
|---|---|---|---|
| 1 | Public-Key Cryptosystems Based on Composite Degree Residuosity Classes Pascal Paillier · Lecture notes in computer science | 10 Oct 2007 | 7,322 |
| 2 | Identity-Based Encryption from the Weil Pairing Dan Boneh, Matthew K. Franklin · Lecture notes in computer science | 2001 | 7,095 |
| 3 | Fully homomorphic encryption using ideal lattices Craig Gentry | 31 May 2009 | 6,742 |
| 4 | The Byzantine Generals Problem Leslie Lamport, Robert E. Shostak, Marshall C. Pease · ACM Transactions on Programming Languages and Systems | Jul 1982 | 6,065 |
| 5 | Combinatorial Optimization: Algorithms and Complexity. David Johnson, Christos H. Papadimitriou, Kenneth Steiglitz · American Mathematical Monthly | Mar 1984 | 6,041 |
| 6 | Ciphertext-Policy Attribute-Based Encryption John Bethencourt, Amit Sahai, Brent R. Waters | May 2007 | 5,026 |
| 7 | A new polynomial-time algorithm for linear programming Narendra K. Karmarkar · COMBINATORICA | Dec 1984 | 4,858 |
| 8 | Random oracles are practical Mihir Bellare, Phillip Rogaway | 1993 | 4,745 |
| 9 | An analysis of approximations for maximizing submodular set functions—I George L. Nemhauser, Laurence A. Wolsey, Marshall L. Fisher · Mathematical Programming | Dec 1978 | 4,553 |
| 10 | Approximate nearest neighbors Piotr Indyk, Rajeev Motwani | 1998 | 4,253 |
| 11 | Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming Michel X. Goemans, David P. Williamson · Journal of the ACM | Nov 1995 | 3,723 |
| 12 | How to play ANY mental game Oded Goldreich, Silvio Micali, Avi Wigderson | 1987 | 3,577 |
| 13 | The Knowledge Complexity of Interactive Proof Systems Shafi Goldwasser, Silvio Micali, Charles Rackoff · SIAM Journal on Computing | Feb 1989 | 3,305 |
| 14 | A threshold of ln n for approximating set cover Uriel Feige · Journal of the ACM | Jul 1998 | 3,149 |
| 15 | Approximation Algorithms for NP-Hard Problems Dorit S. Hochba · ACM SIGACT News | Jun 1997 | 3,143 |
| 16 | Parameterized Complexity Michael R. Fellows · Electronic Notes in Theoretical Computer Science | 2002 | 2,911 |
| 17 | Routing of multipoint connections Bernard M. Waxman · IEEE Journal on Selected Areas in Communications | 1988 | 2,897 |
| 18 | Strategy-proofness and Arrow's conditions: Existence and correspondence theorems for voting procedures and social welfare functions Mark A. Satterthwaite · Journal of Economic Theory | Apr 1975 | 2,884 |
| 19 | An Algorithm for Finding Best Matches in Logarithmic Expected Time Jerome H. Friedman, Jon Louis Bentley, Raphael A. Finkel · ACM Transactions on Mathematical Software | Sep 1977 | 2,828 |
| 20 | The Complexity of Computing the Permanent Leslie Gabriel Valiant · Theoretical Computer Science | 1979 | 2,777 |
| 21 | Greedy Randomized Adaptive Search Procedures Thomas A. Feo, Maurício G. C. Resende · Journal of Global Optimization | Mar 1995 | 2,762 |
| 22 | Graph Implementations for Nonsmooth Convex Programs Michael C. Grant, Stephen Boyd · Lecture notes in control and information sciences | Dec 2007 | 2,753 |
| 23 | A Greedy Heuristic for the Set-Covering Problem Vašek Chvátal · Mathematics of Operations Research | Aug 1979 | 2,604 |
| 24 | Ising formulations of many NP problems Andrew Lucas · Frontiers in Physics | 2014 | 2,596 |
| 25 | Reducibility Among Combinatorial Problems Richard M. Karp | 6 Nov 2009 | 2,505 |
| 26 | Computational Complexity: A Modern Approach Sanjeev Arora, Boaz Barak | 20 Apr 2009 | 2,401 |
| 27 | A fully homomorphic encryption scheme Dan Boneh, Craig Gentry | 2009 | 2,388 |
| 28 | Homomorphic Encryption for Arithmetic of Approximate Numbers Jung Hee Cheon, Andrey Kim, Miran Kim et al. · Lecture notes in computer science | 2017 | 2,376 |
| 29 | On lattices, learning with errors, random linear codes, and cryptography Oded Regev | 22 May 2005 | 2,312 |
| 30 | Security Arguments for Digital Signatures and Blind Signatures David Pointcheval, Jacques Stern · Journal of Cryptology | 21 Mar 2000 | 2,229 |
| 31 | Certificateless Public Key Cryptography Sattam S. Al-Riyami, Kenneth G. Paterson · Lecture notes in computer science | 2003 | 2,226 |
| 32 | Some simplified NP-complete graph problems Michael R. Garey, David S. Johnson, Larry Stockmeyer · Theoretical Computer Science | Feb 1976 | 2,082 |
| 33 | Efficient Identity-Based Encryption Without Random Oracles Brent R. Waters · Lecture notes in computer science | 2005 | 2,036 |
| 34 | Ciphertext-Policy Attribute-Based Encryption: An Expressive, Efficient, and Provably Secure Realization Brent R. Waters · Lecture notes in computer science | 2011 | 1,911 |
| 35 | A new approach to the maximum-flow problem Andrew V. Goldberg, Robert Endre Tarjan · Journal of the ACM | Oct 1988 | 1,896 |
| 36 | Aggregate and Verifiably Encrypted Signatures from Bilinear Maps Dan Boneh, Craig Gentry, Ben Lynn et al. · Lecture notes in computer science | 2003 | 1,827 |
| 37 | (Leveled) fully homomorphic encryption without bootstrapping Zvika Brakerski, Craig Gentry, Vinod Vaikuntanathan | 8 Jan 2012 | 1,791 |
| 38 | Efficient Selective-ID Secure Identity-Based Encryption Without Random Oracles Dan Boneh, Xavier Boyen · Lecture notes in computer science | 2004 | 1,784 |
| 39 | Clustering to minimize the maximum intercluster distance Teofilo F. Gonzalez · Theoretical Computer Science | 1985 | 1,763 |
| 40 | The Lack of A Priori Distinctions Between Learning Algorithms David H. Wolpert · Neural Computation | Oct 1996 | 1,688 |
| 41 | Optimization, approximation, and complexity classes Christos H. Papadimitriou, Mihalis Yannakakis · Journal of Computer and System Sciences | Dec 1991 | 1,673 |
| 42 | Private information retrieval Benny Chor, Eyal Kushilevitz, Oded Goldreich et al. · Journal of the ACM | Nov 1998 | 1,656 |
| 43 | Practical graph isomorphism, II Brendan D. McKay, Adolfo Piperno · Journal of Symbolic Computation | 27 Sep 2013 | 1,646 |
| 44 | Software protection and simulation on oblivious RAMs Oded Goldreich, Rafail Ostrovsky · Journal of the ACM | May 1996 | 1,634 |
| 45 | Graph minors. II. Algorithmic aspects of tree-width Neil R. Robertson, Paul D. Seymour · Journal of Algorithms | Sep 1986 | 1,566 |
| 46 | Homomorphic Encryption from Learning with Errors: Conceptually-Simpler, Asymptotically-Faster, Attribute-Based Craig Gentry, Amit Sahai, Brent R. Waters · Lecture notes in computer science | 2013 | 1,510 |
| 47 | PowerGraph: distributed graph-parallel computation on natural graphs Joseph E. Gonzalez, Yucheng Low, Haijie Gu et al. | 8 Oct 2012 | 1,503 |
| 48 | Efficient Fully Homomorphic Encryption from (Standard) LWE Zvika Brakerski, Vinod Vaikuntanathan | Oct 2011 | 1,481 |
| 49 | Short Signatures Without Random Oracles Dan Boneh, Xavier Boyen · Lecture notes in computer science | 2004 | 1,464 |
| 50 | Conjunctive, Subset, and Range Queries on Encrypted Data Dan Boneh, Brent R. Waters · Lecture notes in computer science | 16 May 2007 | 1,453 |
Citations are OpenAlex's own counts, from its 2026-09-23 snapshot, so the ranking can differ from Google Scholar or Web of Science. A paper is listed for a field when OpenAlex files it under one of the field's topics; retracted papers and papers whose citation count cannot be traced to citing works are left out, and a preprint and the article it became are shown once. Release dates are OpenAlex's: where a source gave only a month or a year, that is what is shown. How the lists are chosen.