A sublinear bipartiteness tester for bounded degree graphs
From MaRDI portal
Publication:1964592
DOI10.1007/s004930050060zbMath0932.68053OpenAlexW2611773579MaRDI QIDQ1964592
Publication date: 21 February 2000
Published in: Combinatorica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s004930050060
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)
Related Items
Fast approximate probabilistically checkable proofs, Random Walks and Forbidden Minors II: A $\mathrm{poly}(d\varepsilon^{-1})$-Query Tester for Minor-Closed Properties of Bounded-Degree Graphs, Small complete minors above the extremal edge density, A lower bound for testing juntas, Testing list \(H\)-homomorphisms, Finding cycles and trees in sublinear time, On the benefits of adaptivity in property testing of dense graphs, Flexible Models for Testing Graph Properties, Unnamed Item, Testing the \((s,t)\) connectivity of graphs and digraphs, Comparing the strength of query types in property testing: the case of \(k\)-colorability, Finding and Using Expanders in Locally Sparse Graphs, Hierarchy theorems for property testing, A Brief Introduction to Property Testing, Introduction to Testing Graph Properties, Testing Eulerianity and connectivity in directed sparse graphs, Hierarchy Theorems for Property Testing, Testing outerplanarity of bounded degree graphs, Non-interactive proofs of proximity, Testing Expansion in Bounded-Degree Graphs, Testing whether a digraph contains \(H\)-free \(k\)-induced subgraphs, Every minor-closed property of sparse graphs is testable, Testing the expansion of a graph, \(\omega\)-regular languages are testable with a constant number of queries, Testing hypergraph colorability, Sublinear-time Algorithms, Comparing the Strength of Query Types in Property Testing: The Case of Testing k-Colorability, Unnamed Item, Fast distributed algorithms for testing graph properties, On the characterization of 1-sided error strongly testable graph properties for bounded-degree graphs, Quantum Property Testing for Bounded-Degree Graphs, On Testing Expansion in Bounded-Degree Graphs, On the Average-Case Complexity of Property Testing, A Brief Introduction to Property Testing, Introduction to Testing Graph Properties, Contemplations on Testing Graph Properties, Another Motivation for Reducing the Randomness Complexity of Algorithms, 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, Planar graphs: Random walks and bipartiteness testing, An explicit construction of graphs of bounded degree that are far from being Hamiltonian
