Tight Bounds for Testing Bipartiteness in General Graphs
From MaRDI portal
Publication:4651520
DOI10.1137/S0097539703436424zbMath1101.68607OpenAlexW1999617330MaRDI QIDQ4651520
Tali Kaufman, Michael Krivelevich, Dana Ron
Publication date: 21 February 2005
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/s0097539703436424
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)
Related Items (28)
Testing Odd-Cycle-Freeness in Boolean Functions ⋮ On Sampling Edges Almost Uniformly ⋮ Finding cycles and trees in sublinear time ⋮ On the benefits of adaptivity in property testing of dense graphs ⋮ Flexible Models for Testing Graph Properties ⋮ Efficient and Near-optimal Algorithms for Sampling Small Connected Subgraphs ⋮ Testing the \((s,t)\) connectivity of graphs and digraphs ⋮ Comparing the strength of query types in property testing: the case of \(k\)-colorability ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Introduction to Testing Graph Properties ⋮ Testing Eulerianity and connectivity in directed sparse graphs ⋮ Distribution-free connectivity testing for sparse graphs ⋮ On the Query Complexity of Testing Orientations for Being Eulerian ⋮ A separation theorem in property testing ⋮ Distributed Testing of Graph Isomorphism in the CONGEST Model. ⋮ Comparing the Strength of Query Types in Property Testing: The Case of Testing k-Colorability ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Fast distributed algorithms for testing graph properties ⋮ Approximating the minimum vertex cover in sublinear time and a connection to distributed algorithms ⋮ Introduction to Testing Graph Properties ⋮ Contemplations on Testing Graph Properties ⋮ A Simple Sublinear-Time Algorithm for Counting Arbitrary Subgraphs via Edge Sampling ⋮ Quantum Chebyshev's Inequality and Applications ⋮ Planar graphs: Random walks and bipartiteness testing ⋮ Unnamed Item ⋮ Testing the supermodular-cut condition
This page was built for publication: Tight Bounds for Testing Bipartiteness in General Graphs
