A sublinear bipartiteness tester for bounded degree graphs

DOI10.1007/S004930050060MaRDI QIDQ1964592zbMATH OpenOpenAlexFDO

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)

Recommendations

scientific article; zbMATH DE number 1775414
Testing subgraphs in large graphs
Approximation, Randomization, and Combinatorial Optimization.. Algorithms and Techniques
Tight Bounds for Testing Bipartiteness in General Graphs
Property testing in bounded degree graphs

Cited in

(48)

Testing whether a digraph contains H-free k-induced subgraphs
Random Walks and Forbidden Minors II: A $\mathrm{poly}(d\varepsilon^{-1})$-Query Tester for Minor-Closed Properties of Bounded-Degree Graphs
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
Non-interactive proofs of proximity
Approximation, Randomization, and Combinatorial Optimization.. Algorithms and Techniques
Contemplations on Testing Graph Properties
Fast approximate probabilistically checkable proofs
Testing Eulerianity and connectivity in directed sparse graphs
Comparing the strength of query types in property testing: the case of testing $k$-colorability
Hierarchy theorems for property testing
On the Randomness Complexity of Property Testing
Hierarchy theorems for property testing
Planar graphs: random walks and bipartiteness testing
A sublinear tester for outerplanarity (and other forbidden minors) with one-sided error
Testing the $(s,t)$ connectivity of graphs and digraphs
Sublinear graph augmentation for fast query implementation
A Brief Introduction to Property Testing
$\omega$-regular languages are testable with a constant number of queries
An explicit construction of graphs of bounded degree that are far from being Hamiltonian
A brief introduction to property testing
The subgraph testing model
On the benefits of adaptivity in property testing of dense graphs
Small complete minors above the extremal edge density
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
Introduction to testing graph properties
scientific article; zbMATH DE number 1775414 (Why is no real title available?)
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
Testing outerplanarity of bounded degree graphs
A lower bound for testing juntas
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

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)