Testing the diameter of graphs

DOI10.1002/rsa.10013zbMath1052.68104MaRDI QIDQ4543626

Michal Parnas, Dana Ron

Publication date: 8 August 2002

Published in: Random Structures & Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1002/rsa.10013

zbMATH Keywords

graph algorithms; property testing

Mathematics Subject Classification ID

68R10: Graph theory (including graph drawing) in computer science

05C85: Graph algorithms (graph-theoretic aspects)

Related Items

Unnamed Item, Introduction to Testing Graph Properties, Testing Euclidean Spanners, Testing Expansion in Bounded-Degree Graphs, Comparing the Strength of Query Types in Property Testing: The Case of Testing k-Colorability, Unnamed Item, On the Communication Complexity Methodology for Proving Lower Bounds on the Query Complexity of Property Testing, Flexible Models for Testing Graph Properties, Planar graphs: Random walks and bipartiteness testing, On Sampling Edges Almost Uniformly, Fast distributed algorithms for testing graph properties, On Approximating the Number of Relevant Variables in a Function, Unnamed Item, Testing the \((s,t)\) connectivity of graphs and digraphs, Testable and untestable classes of first-order formulae, Testing outerplanarity of bounded degree graphs, Shortcutting directed and undirected networks with a degree constraint, Testing convexity properties of tree colorings, Testing Eulerianity and connectivity in directed sparse graphs, Distribution-free connectivity testing for sparse graphs, A separation theorem in property testing, Every minor-closed property of sparse graphs is testable, Dynamic graph stream algorithms in \(o(n)\) space, Comparing the strength of query types in property testing: the case of \(k\)-colorability, On the characterization of 1-sided error strongly testable graph properties for bounded-degree graphs, Testing the supermodular-cut condition, Finding cycles and trees in sublinear time, Introduction to Testing Graph Properties, Contemplations on Testing Graph Properties, On the Query Complexity of Testing Orientations for Being Eulerian, Relational Properties Expressible with One Universal Quantifier Are Testable

Cites Work

• Property testing and its connection to learning and approximation
• Complexity of network synchronization
• Unnamed Item