A sublinear bipartiteness tester for bounded degree graphs
From MaRDI portal
DOI10.1007/S004930050060zbMATH Open0932.68053OpenAlexW2611773579MaRDI QIDQ1964592FDOQ1964592
Authors: Oded Goldreich, Dana Ron 
Publication date: 21 February 2000
Published in: Combinatorica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s004930050060
Recommendations
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)
Cited In (48)
- Testing whether a digraph contains \(H\)-free \(k\)-induced subgraphs
- Lower bounds for testing forbidden induced substructures in bipartite-graph-like combinatorial objects
- Sublinear-time Algorithms
- Tight Bounds for Testing Bipartiteness in General Graphs
- Testing the expansion of a graph
- Approximation, Randomization, and Combinatorial Optimization.. Algorithms and Techniques
- Non-interactive proofs of proximity
- Contemplations on Testing Graph Properties
- Comparing the strength of query types in property testing: the case of testing \(k\)-colorability
- Fast approximate probabilistically checkable proofs
- Testing Eulerianity and connectivity in directed sparse graphs
- Hierarchy theorems for property testing
- Hierarchy theorems for property testing
- On the Randomness Complexity of Property Testing
- Planar graphs: random walks and bipartiteness testing
- A sublinear tester for outerplanarity (and other forbidden minors) with one-sided error
- Sublinear graph augmentation for fast query implementation
- Testing the \((s,t)\) connectivity of graphs and digraphs
- A Brief Introduction to Property Testing
- An explicit construction of graphs of bounded degree that are far from being Hamiltonian
- A brief introduction to property testing
- The subgraph testing model
- \(\omega\)-regular languages are testable with a constant number of queries
- Finding and using expanders in locally sparse 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 benefits of adaptivity in property testing of dense graphs
- Small complete minors above the extremal edge density
- Introduction to testing graph properties
- Title not available (Why is that?)
- Introduction to testing graph properties
- On the randomness complexity of property testing
- 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 Expansion in Bounded-Degree Graphs
- Testing subgraphs in large graphs
- Testing list \(H\)-homomorphisms
- Finding cycles and trees in sublinear time
- Comparing the strength of query types in property testing: the case of \(k\)-colorability
- A lower bound for testing juntas
- Testing outerplanarity of bounded degree graphs
- Testing hypergraph colorability
- On testing expansion in bounded-degree graphs
- On the characterization of 1-sided error strongly testable graph properties for bounded-degree graphs
- Every minor-closed property of sparse graphs is testable
- Quantum property testing for bounded-degree graphs
- On the average-case complexity of property testing
- Another motivation for reducing the randomness complexity of algorithms
- Flexible Models for Testing Graph Properties
- Random Walks and Forbidden Minors II: A $\mathrm{poly}(d\varepsilon^{-1})$-Query Tester for Minor-Closed Properties of Bounded-Degree Graphs
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)
