Topic · Advanced Graph Theory Research
Most cited papers in Advanced Graph Theory Research
What are the most cited papers in Advanced Graph Theory Research?
The most cited paper in Advanced Graph Theory Research is "Reducibility among Combinatorial Problems" (Richard M. Karp, 1972), with 11,108 citations. Next come "A Set of Measures of Centrality Based on Betweenness" (10,473) and "Combinatorial Optimization: Algorithms and Complexity." (6,041).
Showing 50 of 98 papers. Every paper with more than 703 citations is listed.
| # | Paper | ||
|---|---|---|---|
| 1 | Reducibility among Combinatorial Problems Richard M. Karp | 1972 | 11,108 |
| 2 | A Set of Measures of Centrality Based on Betweenness Linton C. Freeman · Sociometry | Mar 1977 | 10,473 |
| 3 | Combinatorial Optimization: Algorithms and Complexity. David Johnson, Christos H. Papadimitriou, Kenneth Steiglitz · American Mathematical Monthly | Mar 1984 | 6,041 |
| 4 | Spectral Graph Theory Fan Chung · Regional conference series in mathematics | 3 Dec 1996 | 5,771 |
| 5 | A new polynomial-time algorithm for linear programming Narendra K. Karmarkar · COMBINATORICA | Dec 1984 | 4,858 |
| 6 | 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 |
| 7 | Algorithm 97: Shortest path Robert W. Floyd · Communications of the ACM | Jun 1962 | 4,080 |
| 8 | Introduction to Graph Theory J. Fields | 2001 | 4,070 |
| 9 | A threshold of ln n for approximating set cover Uriel Feige · Journal of the ACM | Jul 1998 | 3,149 |
| 10 | Parameterized Complexity Michael R. Fellows · Electronic Notes in Theoretical Computer Science | 2002 | 2,911 |
| 11 | Fibonacci heaps and their uses in improved network optimization algorithms Michael L. Fredman, Robert Endre Tarjan · Journal of the ACM | Jul 1987 | 2,695 |
| 12 | A Greedy Heuristic for the Set-Covering Problem Vašek Chvátal · Mathematics of Operations Research | Aug 1979 | 2,604 |
| 13 | Algorithm 457: finding all cliques of an undirected graph Coen Bron, Joep Kerbosch · Communications of the ACM | Sep 1973 | 2,492 |
| 14 | Computational Complexity: A Modern Approach Sanjeev Arora, Boaz Barak | 20 Apr 2009 | 2,401 |
| 15 | Paths, Trees, and Flowers Jack Edmonds · Canadian Journal of Mathematics | 1965 | 2,399 |
| 16 | Approximation algorithms for combinatorial problems David S. Johnson · Journal of Computer and System Sciences | Dec 1974 | 2,229 |
| 17 | Some simplified NP-complete graph problems Michael R. Garey, David S. Johnson, Larry Stockmeyer · Theoretical Computer Science | Feb 1976 | 2,082 |
| 18 | The ellipsoid method and its consequences in combinatorial optimization Martin Grötschel, László Lovász, Alexander Schrijver · COMBINATORICA | Jun 1981 | 2,059 |
| 19 | Distance-Regular Graphs Andries E. Brouwer, Willem H. Haemers · Universitext | 30 Nov 2011 | 1,998 |
| 20 | A new approach to the maximum-flow problem Andrew V. Goldberg, Robert Endre Tarjan · Journal of the ACM | Oct 1988 | 1,896 |
| 21 | Expander graphs and their applications Shlomo Hoory, Nathan Linial, Avi Wigderson · Bulletin of the American Mathematical Society | 7 Aug 2006 | 1,798 |
| 22 | Introduction to graph theory Kathryn L. Fraughnaugh · Networks | Aug 1997 | 1,689 |
| 23 | Optimization, approximation, and complexity classes Christos H. Papadimitriou, Mihalis Yannakakis · Journal of Computer and System Sciences | Dec 1991 | 1,673 |
| 24 | Practical graph isomorphism, II Brendan D. McKay, Adolfo Piperno · Journal of Symbolic Computation | 27 Sep 2013 | 1,646 |
| 25 | New methods to color the vertices of a graph Daniel Brélaz · Communications of the ACM | Apr 1979 | 1,586 |
| 26 | Graph minors. II. Algorithmic aspects of tree-width Neil R. Robertson, Paul D. Seymour · Journal of Algorithms | Sep 1986 | 1,566 |
| 27 | Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms Kellogg S. Booth, George S. Lueker · Journal of Computer and System Sciences | Dec 1976 | 1,507 |
| 28 | Optimization by Simulated Annealing: An Experimental Evaluation; Part I, Graph Partitioning David S. Johnson, C. Aragon, Lyle A. McGeoch et al. · Operations Research | Dec 1989 | 1,474 |
| 29 | The monadic second-order logic of graphs. I. Recognizable sets of finite graphs Bruno Courcelle · Information and Computation | Mar 1990 | 1,474 |
| 30 | On the method of bounded differences Colin McDiarmid · Cambridge University Press eBooks | 3 Aug 1989 | 1,466 |
| 31 | Topological Graph Theory Tomaž Pisanski, Primož Potočnik, Jianer Chen et al. · Discrete mathematics and its applications | 29 Dec 2003 | 1,459 |
| 32 | The Traveling-Salesman Problem and Minimum Spanning Trees Michael Held, Richard M. Karp · Operations Research | Dec 1970 | 1,456 |
| 33 | Unit disk graphs Brent N. Clark, Charles J. Colbourn, David Johnson · Discrete Mathematics | Dec 1990 | 1,446 |
| 34 | Proof verification and the hardness of approximation problems Sanjeev Arora, Carsten Lund, Rajeev Motwani et al. · Journal of the ACM | May 1998 | 1,428 |
| 35 | Which Problems Have Strongly Exponential Complexity? Russell Impagliazzo, Ramamohan Paturi, Francis Zane · Journal of Computer and System Sciences | Dec 2001 | 1,375 |
| 36 | Frequency assignment: Theory and applications William K. Hale · Proceedings of the IEEE | 1980 | 1,354 |
| 37 | The strong perfect graph theorem Maria Chudnovsky, Neil R. Robertson, Paul D. Seymour et al. · Annals of Mathematics | Jul 2006 | 1,300 |
| 38 | Graph Minors .XIII. The Disjoint Paths Problem Neil R. Robertson, Paul D. Seymour · Journal of Combinatorial Theory Series B | 1995 | 1,298 |
| 39 | Solution of a Large-Scale Traveling-Salesman Problem Vašek Chvátal, William J. Cook, George B. Dantzig et al. | 6 Nov 2009 | 1,272 |
| 40 | Complexity of Finding Embeddings in a k -Tree Stefan Arnborg, Derek Gordon Corneil, Andrzej Proskurowski · SIAM Journal on Algebraic and Discrete Methods | Apr 1987 | 1,208 |
| 41 | A fast algorithm for Steiner trees Lawrence T. Kou, George Markowsky, Leonard Berman · Acta Informatica | 1981 | 1,197 |
| 42 | Worst-Case Analysis of a New Heuristic for the Travelling Salesman Problem Nicos Christofides · Operations Research Forum | Mar 2022 | 1,152 |
| 43 | Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems Sanjeev Arora · Journal of the ACM | Sep 1998 | 1,150 |
| 44 | Optimum Distribution of Switching Centers in a Communication Network and Some Related Graph Theoretic Problems S. L. Hakimi · Operations Research | Jun 1965 | 1,140 |
| 45 | Approximation Algorithms for Connected Dominating Sets Suvajyoti Guha, Samir Khuller · Algorithmica | Apr 1998 | 1,138 |
| 46 | A partial k-arboretum of graphs with bounded treewidth Hans L. Bodlaender · Theoretical Computer Science | Dec 1998 | 1,132 |
| 47 | How to Draw a Graph W. T. Tutte · Proceedings of the London Mathematical Society | 1963 | 1,126 |
| 48 | Selected Topics in Column Generation Marco E. Lübbecke, Jacques Desrosiers · Operations Research | Dec 2005 | 1,109 |
| 49 | Graph theory with applications to engineering and computer science N.R. Malik · Proceedings of the IEEE | Oct 1975 | 1,048 |
| 50 | A Contribution to the Theory of Chromatic Polynomials W. T. Tutte · Canadian Journal of Mathematics | 1954 | 1,037 |
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.