The DOI matches its Crossref record; 64 of the 64 references it cites were found in a registry or an index.
The maximum clique problem
Overview
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
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
Cites
Geometric Algorithms and Combinatorial Optimization
Grötschel, M., Lovász, L., & Schrijver, A. (1988) · Algorithms and Combinatorics · doi:10.1007/978-3-642-97881-4 · Cited by 3,431
Integer and Combinatorial Optimization
Nemhauser, G., & Wolsey, L. (1988) · Wiley eBooks · doi:10.1002/9781118627372 · Cited by 3,176
A Greedy Heuristic for the Set-Covering Problem
Chvatal, V. (1979) · Mathematics of Operations Research · doi:10.1287/moor.4.3.233 · Cited by 2,581
Algorithm 457: finding all cliques of an undirected graph
Bron, C., & Kerbosch, J. (1973) · Communications of the ACM · doi:10.1145/362342.362367 · Cited by 2,452
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
The Complexity of Enumeration and Reliability Problems
Valiant, L. G. (1979) · SIAM Journal on Computing · doi:10.1137/0208032 · Cited by 2,076
The ellipsoid method and its consequences in combinatorial optimization
Grötschel, M., Lovász, L., & Schrijver, A. (1981) · Combinatorica · doi:10.1007/bf02579273 · Cited by 2,011
On the Shannon capacity of a graph
Lovasz, L. (1979) · IEEE Transactions on Information Theory · doi:10.1109/tit.1979.1055985 · Cited by 1,624
New methods to color the vertices of a graph
Brélaz, D. (1979) · Communications of the ACM · doi:10.1145/359094.359101 · Cited by 1,567
The zero error capacity of a noisy channel
Shannon, C. (1956) · IEEE Transactions on Information Theory · doi:10.1109/tit.1956.1056798 · Cited by 1,468
A Separator Theorem for Planar Graphs
Lipton, R. J., & Tarjan, R. E. (1979) · SIAM Journal on Applied Mathematics · doi:10.1137/0136016 · Cited by 1,359
Algorithmic Aspects of Vertex Elimination on Graphs
Rose, D. J., Tarjan, R. E., & Lueker, G. S. (1976) · SIAM Journal on Computing · doi:10.1137/0205021 · Cited by 1,203
A Simple Parallel Algorithm for the Maximal Independent Set Problem
Luby, M. (1986) · SIAM Journal on Computing · doi:10.1137/0215074 · Cited by 1,147
Tarjan, R. E., & Yannakakis, M. (1984) · SIAM Journal on Computing · doi:10.1137/0213035 · Cited by 1,058
Dirac, G. A. (1961) · Abhandlungen aus dem Mathematischen Seminar der Universität Hamburg · doi:10.1007/bf02992776 · Cited by 927
Moon, J. W., & Moser, L. (1965) · Israel Journal of Mathematics · doi:10.1007/bf02760024 · Cited by 837
A fast and simple randomized parallel algorithm for the maximal independent set problem
Alon, N., Babai, L., & Itai, A. (1986) · Journal of Algorithms · doi:10.1016/0196-6774(86)90019-2 · Cited by 823
On generating all maximal independent sets
Johnson, D. S., Yannakakis, M., & Papadimitriou, C. H. (1988) · Information Processing Letters · doi:10.1016/0020-0190(88)90065-8 · Cited by 771
Maxima for Graphs and a New Proof of a Theorem of Turán
Motzkin, T. S., & Straus, E. G. (1965) · Canadian Journal of Mathematics · doi:10.4153/cjm-1965-053-6 · Cited by 710
Vertex packings: Structural properties and algorithms
Nemhauser, G. L., & Trotter, L. E. (1975) · Mathematical Programming · doi:10.1007/bf01580444 · Cited by 664
Applications of a Planar Separator Theorem
Lipton, R. J., & Tarjan, R. E. (1980) · SIAM Journal on Computing · doi:10.1137/0209046 · Cited by 640
On certain polytopes associated with graphs
Chvátal, V. (1975) · Journal of Combinatorial Theory Series B · doi:10.1016/0095-8956(75)90041-6 · Cited by 604
On the facial structure of set packing polyhedra
Padberg, M. W. (1973) · Mathematical Programming · doi:10.1007/bf01580121 · Cited by 596
Probabilistic construction of deterministic algorithms: Approximating packing integer programs
Raghavan, P. (1988) · Journal of Computer and System Sciences · doi:10.1016/0022-0000(88)90003-7 · Cited by 554
Constrained Global Optimization: Algorithms and Applications
(1987) · Lecture Notes in Computer Science · doi:10.1007/bfb0000035 · Cited by 519
Triangulated graphs and the elimination process
Rose, D. J. (1970) · Journal of Mathematical Analysis and Applications · doi:10.1016/0022-247x(70)90282-9 · Cited by 500
Finding a Maximum Independent Set
Tarjan, R. E., & Trojanowski, A. E. (1977) · SIAM Journal on Computing · doi:10.1137/0206038 · Cited by 474
On maximal independent sets of vertices in claw-free graphs
Minty, G. J. (1980) · Journal of Combinatorial Theory, Series B · doi:10.1016/0095-8956(80)90074-x · Cited by 463
A new table of constant weight codes
Brouwer, A. E., Shearer, J. B., Sloane, N. J. A., & Smith, W. D. (1990) · IEEE Transactions on Information Theory · doi:10.1109/18.59932 · Cited by 422
An Algorithmic Theory of Numbers, Graphs and Convexity
Lovász, L. (1986) · Society for Industrial and Applied Mathematics eBooks · doi:10.1137/1.9781611970203 · Cited by 358
Connectivity and Generalized Cliques in Sociometric Group Structure
Luce, R. D. (1950) · Psychometrika · doi:10.1007/bf02289199 · Cited by 343
An Input-Output Approach to Clique Identification
Hubbell, C. H. (1965) · Sociometry · doi:10.2307/2785990 · Cited by 342
Bollobas, B., & Erdös, P. (1976) · Mathematical Proceedings of the Cambridge Philosophical Society · doi:10.1017/s0305004100053056 · Cited by 321
Finding a Maximum Clique in an Arbitrary Graph
Balas, E., & Yu, C. S. (1986) · SIAM Journal on Computing · doi:10.1137/0215075 · Cited by 295
Generating All Maximal Independent Sets: NP-Hardness and Polynomial-Time Algorithms
Lawler, E. L., Lenstra, J. K., & Kan, A. H. G. R. (1980) · SIAM Journal on Computing · doi:10.1137/0209042 · Cited by 285
Algorithme de recherche d'un stable de cardinalite maximum dans un graphe sans etoile
Sbihi, N. (1980) · Discrete Mathematics · doi:10.1016/0012-365x(90)90287-r · Cited by 276
Efficient algorithms for interval graphs and circular‐arc graphs
Gupta, U. I., Lee, D. T., & Leung, J. Y. ‐. (1982) · Networks · doi:10.1002/net.3230120410 · Cited by 274
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
An Analysis of Some Graph Theoretical Cluster Techniques
Augustson, J. G., & Minker, J. (1970) · Journal of the ACM · doi:10.1145/321607.321608 · Cited by 229
Bonner, R. E. (1964) · IBM Journal of Research and Development · doi:10.1147/rd.81.0022 · Cited by 209
On the independence number of random graphs
Frieze, A. M. (1990) · Discrete Mathematics · doi:10.1016/0012-365x(90)90149-c · Cited by 187
A class of facet producing graphs for vertex packing polyhedra
Trotter, L. E. (1975) · Discrete Mathematics · doi:10.1016/0012-365x(75)90077-1 · Cited by 161
Hard Enumeration Problems in Geometry and Combinatorics
Linial, N. (1986) · SIAM Journal on Algebraic and Discrete Methods · doi:10.1137/0607036 · Cited by 130
Keller’s cube-tiling conjecture is false in high dimensions
Lagarias, J. C., & Shor, P. W. (1992) · Bulletin of the American Mathematical Society · doi:10.1090/s0273-0979-1992-00318-x · Cited by 114
Motif recognition and alignment for many sequences by comparison of dot-matrices
Vingron, M., & Argos, P. (1991) · Journal of Molecular Biology · doi:10.1016/0022-2836(91)90871-3 · Cited by 112
Covering, Packing and Knapsack Problems
Padberg, M. W. (1979) · Annals of discrete mathematics · doi:10.1016/s0167-5060(08)70831-8 · Cited by 110
Covers and packings in a family of sets
Edmonds, J. (1962) · Bulletin of the American Mathematical Society · doi:10.1090/s0002-9904-1962-10791-5 · Cited by 101
Optimizing weakly triangulated graphs
Hayward, R., Hoàng, C. T., & Maffray, F. (1989) · Graphs and Combinatorics · doi:10.1007/bf01788689 · Cited by 88
Test case generators and computational results for the maximum clique problem
Hasselberg, J., Pardalos, P. M., & Vairaktarakis, G. L. (1993) · Journal of Global Optimization · doi:10.1007/bf01096415 · Cited by 68
Self-citationEfficient parallel algorithms for chordal graphs
Klein, P. N. (1988) · Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.1988.21933 · Cited by 67
Parallel algorithms for finding a near-maximum independent set of a circle graph
Takefuji, Y., Chen, L.-L., Lee, K. C., & Huffman, J. E. (1990) · IEEE Transactions on Neural Networks · doi:10.1109/72.80251 · Cited by 62
An Optimal Algorithm for Finding a Maximum Independent Set of a Circular-Arc Graph
Masuda, S., & Nakajima, K. (1988) · SIAM Journal on Computing · doi:10.1137/0217003 · Cited by 59
Determining the Stability Number of a Graph
Chvátal, V. (1977) · SIAM Journal on Computing · doi:10.1137/0206046 · Cited by 55
A Note on the Detection of Cliques in Valued Graphs
Doreian, P. (1969) · Sociometry · doi:10.2307/2786266 · Cited by 49
On the Greedy Heuristic for Continuous Covering and Packing Problems
Fisher, M. L., & Wolsey, L. A. (1982) · SIAM Journal on Algebraic and Discrete Methods · doi:10.1137/0603059 · Cited by 48
On the Complexity of Set Packing Polyhedra
Padberg, M. W. (1977) · Annals of discrete mathematics · doi:10.1016/s0167-5060(08)70750-7 · Cited by 46
Approximating maximum independent sets by excluding subgraphs
Boppana, R. B., & Halldórsson, M. M. (1990) · Lecture notes in computer science · doi:10.1007/3-540-52846-6_74 · Cited by 46
On the integer-valued variables in the linear vertex packing problem
Picard, J., & Queyranne, M. (1977) · Mathematical Programming · doi:10.1007/bf01593772 · Cited by 46
A polynomial algorithm for maximum weighted vertex packings on graphs without long odd cycles
Hsu, W., Ikura, Y., & Nemhauser, G. L. (1981) · Mathematical Programming · doi:10.1007/bf01589347 · Cited by 33
On the complexity of approximating the independent set problem
Berman, P., & Schnitger, G. (1989) · Lecture notes in computer science · doi:10.1007/bfb0028990 · Cited by 30
Active constraints, indefinite quadratic test problems, and complexity
Hager, W. W., Pardalos, P. M., Roussos, I. M., & Sahinoglou, H. (1991) · Journal of Optimization Theory and Applications · doi:10.1007/bf00940067 · Cited by 24
Self-citationEfficiently approximating max-clique in a Hopfield-style network
Jagota, A. (2003) · International Joint Conference on Neural Networks (IJCNN) · doi:10.1109/ijcnn.1992.227000 · Cited by 13
The maximum independent set problem for cubic planar graphs
Burns, J. E. (1989) · Networks · doi:10.1002/net.3230190307 · Cited by 13
Maximum internally stable sets of a graph
Hakimi, S. L., & Frank, H. (1969) · Journal of Mathematical Analysis and Applications · doi:10.1016/0022-247x(69)90233-9 · Cited by 12
Cited by
Graph embedding techniques, applications, and performance: A survey
Goyal, P., & Ferrara, E. (2018) · Knowledge-Based Systems · doi:10.1016/j.knosys.2018.03.022 · Cited by 1,801
The worst-case time complexity for generating all maximal cliques and computational experiments
Tomita, E., Tanaka, A., & Takahashi, H. (2006) · Theoretical Computer Science · doi:10.1016/j.tcs.2006.06.015 · Cited by 771
The unconstrained binary quadratic programming problem: a survey
Kochenberger, G., Hao, J.-K., Glover, F., Lewis, M., Lü, Z., Wang, H., & Wang, Y. (2014) · Journal of Combinatorial Optimization · doi:10.1007/s10878-014-9734-0 · Cited by 473
Quantum Bridge Analytics I: a tutorial on formulating and using QUBO models
Glover, F., Kochenberger, G., & Du, Y. (2019) · 4OR · doi:10.1007/s10288-019-00424-y · Cited by 298
Applications of near-term photonic quantum computers: software and algorithms
Bromley, T. R., Arrazola, J. M., Jahangiri, S., Izaac, J., Quesada, N., Gran, A. D., Schuld, M., Swinarton, J., Zabaneh, Z., & Killoran, N. (2020) · Quantum Science and Technology · doi:10.1088/2058-9565/ab8504 · Cited by 128
Metadata
- Authors
- Pardalos, P. M., & Xue, J.
- Venue
- Journal of Global Optimization
- Published
- 1994-04
- Volume
- 4
- Issue
- 3
- Pages
- 301-328
- ISSN
- 0925-5001 (ISSN-L)
- 1573-2916
- OpenAlex
- W3136668146
- Cited by
- 382
- References
- 64
- FWCI
- 9.21
- Type
- journal article
- 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.
