A Sublinear Bipartiteness Tester for Bounded Degree Graphs

• 1 March 1999
• journal article
• Published by Springer Nature in Combinatorica
• Vol. 19  (3) , 335-373
• https://doi.org/10.1007/s004930050060

Abstract

Keywords

• GRAPH ALGORITHMS
• PROPERTY TESTING
• BOUNDED DEGREE GRAPH
• EX- PANSION OF GRAPHS.
• SUBLINEAR BIPARTITENESS TESTER
• APPROXIMATION ALGORITHMS
• RANDOM WALKS ON GRAPHS
• BIPARTITE GRAPH