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

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, 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, 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, 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

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