The DOI matches its Crossref record; 7 of the 7 references it cites were found in a registry or an index.
Color-coding
Open accessAbstract
We describe a novel randomized method.the method of cobm-coding for finding simple paths and cycles of a specified length k, and other small subgraphs, within a gwen graph G = ( 1', E).The randomized algorithms obtained using this method can be derandomlzcd using kmihes of petfect hash f~wtctmns.Using the color-coding method we obtain.m particular, the following new results:-For every fixed k, if a graph G = (V.E) contains a simple cycle of size exactly k, then such a cycle can be found m either 0( V'") expected time or 0( L'"' log P') worst-case t]mc, where w < ?,376 ]s the exponent of matrrx multiplication.(Here and in what follows we use V and E instead of Ib' and IEI whenever no confusion may arise.)-For every fwed k, if a planar graph G = (P-, E) contains a simple cycle of size e.wrctly k, then such a cycle cmr be found m either 0(V) expected time or 0( V log V ) worst-case time.The same algorithm applies, in fact, not only to planar gmphs, but to any mino~closed family of graphs which is not the f~mily of all graphs, -If a grdph G = (V, E) contains a subgraph isomorphic to a boanded tree-width graph H = ( V~, E~) where IV, I = O(log V), then such a copy of H can be found in polyzonzml tune.This was not prewously known even if H were Just a path of length O(log V).These results improve upon previous results of many authors.The third result resolves in the affirmative a conjecture of Papadimltnou and Yannakakis that the LOG PATH problem is m P. We can show that it is even in NC.
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
Cites
Graph minors. II. Algorithmic aspects of tree-width
Robertson, N., & Seymour, P. D. (1986) · Journal of Algorithms · doi:10.1016/0196-6774(86)90023-4 · Cited by 1,542
The NP-completeness column: An ongoing guide
Johnson, D. S. (1986) · Journal of Algorithms · doi:10.1016/0196-6774(86)90020-9 · Cited by 794
Storing a Sparse Table with 0 (1) Worst Case Access Time
Fredman, M. L., Komlós, J., & Szemerédi, E. (1984) · Journal of the ACM · doi:10.1145/828.1884 · Cited by 748
Finding and counting given length cycles
Alon, N., Yuster, R., & Zwick, U. (1997) · Algorithmica · doi:10.1007/bf02523189 · Cited by 608
Self-citationSimple Constructions of Almost k‐wise Independent Random Variables
Alon, N., Goldreich, O., Håstad, J., & Peralta, R. (1992) · Random Structures & Algorithms · doi:10.1002/rsa.3240030308 · Cited by 556
Self-citationFinding a Minimum Circuit in a Graph
Itai, A., & Rodeh, M. (1978) · SIAM Journal on Computing · doi:10.1137/0207033 · Cited by 391
Construction of asymptotically good low-rate error-correcting codes through pseudo-random graphs
Alon, N., Bruck, J., Naor, J., Naor, M., & Roth, R. M. (1992) · IEEE Transactions on Information Theory · doi:10.1109/18.119713 · Cited by 257
Self-citation
Cited by
Invitation to Fixed-Parameter Algorithms
Niedermeier, R. (2006) · doi:10.1093/acprof:oso/9780198566076.001.0001 · Cited by 1,668
The misuse of colour in science communication
Crameri, F., Shephard, G. E., & Heron, P. J. (2020) · Nature Communications · doi:10.1038/s41467-020-19160-7 · Cited by 1,110
Finding and counting given length cycles
Alon, N., Yuster, R., & Zwick, U. (1997) · Algorithmica · doi:10.1007/bf02523189 · Cited by 608
Self-citationInfusion Nursing Standards of Practice
Gorski, L. A. (2007) · Journal of Infusion Nursing · doi:10.1097/01.nan.0000270673.13439.95 · Cited by 602
PARAMETERIZED COMPLEXITY THEORY
Niedermeier, R. (2006) · Invitation to Fixed-Parameter Algorithms · doi:10.1093/acprof:oso/9780198566076.003.0013 · Cited by 574
Modeling cellular machinery through biological network comparison
Sharan, R., & Ideker, T. (2006) · Nature Biotechnology · doi:10.1038/nbt1196 · Cited by 559
A new algorithm for optimal 2-constraint satisfaction and its implications
Williams, R. (2005) · Theoretical Computer Science · doi:10.1016/j.tcs.2005.09.023 · Cited by 386
Computational approaches for detecting protein complexes from protein interaction networks: a survey
Li, X., Wu, M., Kwoh, C.-K., & Ng, S.-K. (2010) · BMC Genomics · doi:10.1186/1471-2164-11-s1-s3 · Cited by 349
Threshold Ring Signatures and Applications to Ad-hoc Groups
Bresson, E., Stern, J., & Szydlo, M. (2002) · Lecture Notes in Computer Science · doi:10.1007/3-540-45708-9_30 · Cited by 311
The discovery of integrated gene networks for autism and related disorders
Hormozdiari, F., Penn, O., Borenstein, E., & Eichler, E. E. (2015) · Genome Research · doi:10.1101/gr.178855.114 · Cited by 249
Efficient Algorithms for Detecting Signaling Pathways in Protein Interaction Networks
Scott, J., Ideker, T., Karp, R. M., & Sharan, R. (2006) · Journal of Computational Biology · doi:10.1089/cmb.2006.13.133 · Cited by 269
Metadata
- Authors
- Alon, N., Yuster, R., & Zwick, U.
- Venue
- Journal of the ACM
- Published
- 1995-07
- Volume
- 42
- Issue
- 4
- Pages
- 844-856
- ISSN
- 0004-5411 (ISSN-L)
- 1557-735X
- OpenAlex
- W2296148711
- Cited by
- 1,002
- References
- 7
- FWCI
- 5.61
- Type
- journal article
- Language
- en
- Open access
- bronze
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.