A sublinear bipartiteness tester for bounded degree graphs
We present a sublinear-time algorithm for testing whether a bounded degree graph is bipartite or far from being bipartite. Graphs are represented by incidence lists of bounded length and the testing algorithm can perform queries of the form ``who is the \(i\)th neighbour of vertex \(v\). The tester should determine with high probability whether the graph is bipartite or \(\varepsilon\)-far from bipartite for any given distance parameter \(\varepsilon\). Distance between graphs is defined to be the fraction of entries on which the graphs differ in their incidence-lists representation. Their algorithm uses random walk technique and its performance is tight (in a sense explained in the paper).
- Non-interactive proofs of proximity
- Sublinear graph augmentation for fast query implementation
- Testing hypergraph colorability
- Fast approximate probabilistically checkable proofs
- Comparing the strength of query types in property testing: the case of \(k\)-colorability
- On the characterization of 1-sided error strongly testable graph properties for bounded-degree graphs
- A lower bound for testing juntas
- Finding cycles and trees in sublinear time
- 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
- Small complete minors above the extremal edge density
- Random walks and forbidden minors. I: An \(n^{1/2+o(1)}\)-query one-sided tester for minor closed properties on bounded degree graphs
- Testing list H-homomorphisms
- Lower bounds for testing forbidden induced substructures in bipartite-graph-like combinatorial objects
- On the Randomness Complexity of Property Testing
- Testing the \((s,t)\) connectivity of graphs and digraphs
- Hierarchy theorems for property testing
- scientific article; zbMATH DE number 1775414 (Why is no real title available?)
- Finding and using expanders in locally sparse graphs
- Tight Bounds for Testing Bipartiteness in General Graphs
- Testing subgraphs in large graphs
- Testing Expansion in Bounded-Degree Graphs
- A brief introduction to property testing
- Sublinear-time Algorithms
- Introduction to testing graph properties
- Comparing the strength of query types in property testing: the case of testing \(k\)-colorability
- Hierarchy theorems for property testing
- Testing outerplanarity of bounded degree graphs
- A sublinear tester for outerplanarity (and other forbidden minors) with one-sided error
- The subgraph testing model
- Flexible Models for Testing Graph Properties
- Planar graphs: random walks and bipartiteness testing
- An explicit construction of graphs of bounded degree that are far from being Hamiltonian
- Random Walks and Forbidden Minors II: A $\mathrm{poly}(d\varepsilon^{-1})$-Query Tester for Minor-Closed Properties of Bounded-Degree Graphs
- Approximation, Randomization, and Combinatorial Optimization.. Algorithms and Techniques
- On the benefits of adaptivity in property testing of dense 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
- On the randomness complexity of property testing
- Testing Eulerianity and connectivity in directed sparse graphs
- \(\omega\)-regular languages are testable with a constant number of queries
- Narrowing the \textsf{LOCAL-CONGEST} gaps in sparse networks via expander decompositions
- 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
This page was built for publication: A sublinear bipartiteness tester for bounded degree graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1964592)
