Finding cycles and trees in sublinear time

DOI10.1002/rsa.20462zbMath1307.05210arXiv1007.4230OpenAlexW1648776928MaRDI QIDQ2925521

Dana Ron, Asaf Shapira, Christian Sohler, C. Seshadhri, Oded Goldreich, Artur Czumaj

Publication date: 16 October 2014

Published in: Random Structures & Algorithms (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1007.4230

zbMATH Keywords

property testingbounded-degree graphssublinear-time algorithmsone-sided versus two-sided error probability

Mathematics Subject Classification ID

Trees (05C05) Paths and cycles (05C38) Graph minors (05C83) Distance in graphs (05C12) Graph algorithms (graph-theoretic aspects) (05C85) Randomized algorithms (68W20)

Related Items

Random Walks and Forbidden Minors II: A $\mathrm{poly}(d\varepsilon^{-1})$-Query Tester for Minor-Closed Properties of Bounded-Degree Graphs, Stability structures of conjunctive Boolean networks, Finding cycles and trees in sublinear time, Property testing of planarity in the \textsf{CONGEST} model, Unnamed Item, Unnamed Item, Non-interactive proofs of proximity, On the characterization of 1-sided error strongly testable graph properties for bounded-degree graphs, Random Walks and Forbidden Minors I: An $n^{1/2+o(1)}$-Query One-Sided Tester for Minor Closed Properties on Bounded Degree Graphs, Random Walks and Forbidden Minors I: An $n^{1/2+o(1)}$-Query One-Sided Tester for Minor Closed Properties on Bounded Degree Graphs

Cites Work

• Unnamed Item
• The disjoint paths problem in quadratic time
• On the randomness complexity of property testing
• Graph minors. XX: Wagner's conjecture
• Expanding graphs contain all small trees
• Graph minors. XIII: The disjoint paths problem
• A sublinear bipartiteness tester for bounded degree graphs
• Finding cycles and trees in sublinear time
• Property testing and its connection to learning and approximation
• On the girth of hamiltonian weakly pancyclic graphs
• Three theorems regarding testing graph properties
• Testing satisfiability
• Testing the diameter of graphs
• Tight Bounds for Testing Bipartiteness in General Graphs
• lgorithmic and Analysis Techniques in Property Testing
• Property testing in bounded degree graphs