A sublinear bipartiteness tester for bounded degree graphs
type: Item
instance of: scholarly article
title: A sublinear bipartiteness tester for bounded degree graphs
zbMATH Open document ID: 0932.68053
author: Oded Goldreich
author: Dana Ron
published in: Combinatorica
publication date: 2000-02-21T00:00:00Z
review text: 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).
reviewed by: András Recski
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 68R10
zbMATH DE Number: 1404391
zbMATH Keywords: bipartiteness tester
MaRDI profile type: Publication
full work available at URL: s004930050060
OpenAlex ID: W2611773579
DOI: 10.1007/S004930050060
description: scientific article; zbMATH DE number 1404391