zbMATH — the first resource for mathematics

Testing the diameter of graphs. (English) Zbl 0945.05057
Hochbaum, Dorit (ed.) et al., Randomization, approximation, and combinatorial optimization. Algorithms and techniques. 3rd international workshop on randomization and approximation techniques in computer science, and 2nd international workshop on approximation algorithms for combinatorial optimization problems RANDOM-APPROX ’99. Berkeley, CA, USA, August 8-11, 1999. Proceedings. Berlin: Springer. Lect. Notes Comput. Sci. 1671, 85-96 (1999).
Summary: We propose a general model for testing graph properties, which extends and simplifies the bounded degree model of O. Goldreich and D. Ron (1997). In this model we present a family of algorithms that test whether the diameter of a graph is bounded by a given parameter \(D\), or is \(\varepsilon\)-far from any graph with diameter at most \(\beta(D)\). The function \(\beta(D)\) ranges between \(D+4\) and \(4D+2\), depending on the algorithm. All our algorithms run in time polynomial in \(1/\varepsilon\).
For the entire collection see [Zbl 0921.00035].

05C85 Graph algorithms (graph-theoretic aspects)
68R10 Graph theory (including graph drawing) in computer science