The DOI matches its Crossref record; 19 of the 19 references it cites were found in a registry or an index.
The geometry of graphs and some of its algorithmic applications
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
(1973) · CERN Document Server (European Organization for Nuclear Research) · Cited by 12,895
Pattern Classification and Scene Analysis
Thompson, M., Duda, R. O., & Hart, P. E. (1974) · Leonardo · doi:10.2307/1573081 · Cited by 4,495
Extensions of Lipschitz mappings into a Hilbert space
Johnson, W. B., & Lindenstrauss, J. (1984) · Contemporary Mathematics · doi:10.1090/conm/026/737400 · Cited by 2,523
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
Through the Looking-Glass: And What Alice Found There
Carroll, L. (1871) · University of Florida Digital Collections (University of Florida) · Cited by 1,322
van Lint, J. H., & Wilson, R. M. (2001) · Cambridge University Press eBooks · doi:10.1017/cbo9780511987045 · Cited by 1,185
Theory and Applications of Distance Geometry
Blumenthal, L. M. (1970) · CERN Document Server (European Organization for Nuclear Research) · Cited by 1,003
The Volume of Convex Bodies and Banach Space Geometry
Pisier, G. (1989) · Cambridge University Press eBooks · doi:10.1017/cbo9780511662454 · Cited by 967
On lipschitz embedding of finite metric spaces in Hilbert space
Bourgain, J. (1985) · Israel Journal of Mathematics · doi:10.1007/bf02776078 · Cited by 560
Leighton, T., & Rao, S. (1988) · [Proceedings 1988] 29th Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.1988.21958 · Cited by 395
The Johnson-Lindenstrauss lemma and the sphericity of some graphs
Frankl, P., & Maehara, H. (1988) · Journal of Combinatorial Theory, Series B · doi:10.1016/0095-8956(88)90043-3 · Cited by 299
.879-approximation algorithms for MAX CUT and MAX 2SAT
Goemans, M. X., & Williamson, D. P. (1994) · Proceedings of the twenty-sixth annual ACM symposium on Theory of computing - STOC '94 · doi:10.1145/195058.195216 · Cited by 234
The geometry of graphs and some of its algorithmic applications
Linial, N., London, E., & Rabinovich, Y. (2002) · Proceedings 35th Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.1994.365733 · Cited by 190
Self-citationComplexity: Knots, Colourings and Countings
Welsh, D. (1993) · Cambridge University Press eBooks · doi:10.1017/cbo9780511752506 · Cited by 186
878-approximation Algorithms for MAX CUT and MAX 2SAT
Goemans, M. X. (1994) · Symposium on the Theory of Computing · Cited by 173
Approximate graph coloring by semidefinite programming
Karger, D. R., Motwani, R., & Sudan, M. (2002) · Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.1994.365710 · Cited by 99
Approximate max-flow min-(multi)cut theorems and their applications
Garg, N., Vazirani, V. V., & Yannakakis, M. (1993) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/167088.167266 · Cited by 85
Separators in two and three dimensions
Miller, G. L., & Thurston, W. P. H. (1990) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/100216.100255 · Cited by 78
Computing the center of planar point sets
Matoušek, J. (1991) · DIMACS series in discrete mathematics and theoretical computer science · doi:10.1090/dimacs/006/14 · Cited by 60
Cited by
Exact Matrix Completion via Convex Optimization
Candès, E. J., & Recht, B. (2009) · Foundations of Computational Mathematics · doi:10.1007/s10208-009-9045-5 · Cited by 4,877
Approximate nearest neighbors: towards removing the curse of dimensionality
Indyk, P., & Motwani, R. (1998) · Proceedings of the thirtieth annual ACM symposium on Theory of computing - STOC '98 · doi:10.1145/276698.276876 · Cited by 4,188
Expander graphs and their applications
Hoory, S., Linial, N., & Wigderson, A. (2006) · Bulletin of the American Mathematical Society · doi:10.1090/s0273-0979-06-01126-8 · Cited by 1,723
Self-citationThe Design of Approximation Algorithms
Williamson, D. P., & Shmoys, D. B. (2011) · Cambridge University Press eBooks · doi:10.1017/cbo9780511921735 · Cited by 1,301
Fixed point and Bregman iterative methods for matrix rank minimization
Ma, S., Goldfarb, D., & Chen, L. (2011) · Mathematical Programming · doi:10.1007/s10107-009-0306-5 · Cited by 1,048
Metadata
- Authors
- Linial, N., London, E., & Rabinovich, Y.
- Venue
- Combinatorica
- Published
- 1995-06
- Volume
- 15
- Issue
- 2
- Pages
- 215-245
- ISSN
- 0209-9683 (ISSN-L)
- 1439-6912
- OpenAlex
- W2176446742
- Cited by
- 952
- References
- 19
- FWCI
- 14.28
- 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.