Testing the diameter of graphs
From MaRDI portal
Publication:4543626
DOI10.1002/rsa.10013zbMath1052.68104MaRDI QIDQ4543626
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
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