Testing the diameter of graphs
From MaRDI portal
Publication:4543626
DOI10.1002/rsa.10013zbMath1052.68104OpenAlexW4248878005MaRDI 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
Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items (31)
On Sampling Edges Almost Uniformly ⋮ Finding cycles and trees in sublinear time ⋮ On the Communication Complexity Methodology for Proving Lower Bounds on the Query Complexity of Property Testing ⋮ Flexible Models for Testing Graph Properties ⋮ Testing the \((s,t)\) connectivity of graphs and digraphs ⋮ Comparing the strength of query types in property testing: the case of \(k\)-colorability ⋮ Unnamed Item ⋮ Testable and untestable classes of first-order formulae ⋮ Unnamed Item ⋮ Introduction to Testing Graph Properties ⋮ Testing Eulerianity and connectivity in directed sparse graphs ⋮ Distribution-free connectivity testing for sparse graphs ⋮ On the Query Complexity of Testing Orientations for Being Eulerian ⋮ Testing Euclidean Spanners ⋮ Testing outerplanarity of bounded degree graphs ⋮ Dynamic graph stream algorithms in \(o(n)\) space ⋮ Shortcutting directed and undirected networks with a degree constraint ⋮ A separation theorem in property testing ⋮ Testing Expansion in Bounded-Degree Graphs ⋮ Every minor-closed property of sparse graphs is testable ⋮ Testing convexity properties of tree colorings ⋮ Comparing the Strength of Query Types in Property Testing: The Case of Testing k-Colorability ⋮ Unnamed Item ⋮ Fast distributed algorithms for testing graph properties ⋮ On Approximating the Number of Relevant Variables in a Function ⋮ On the characterization of 1-sided error strongly testable graph properties for bounded-degree graphs ⋮ Introduction to Testing Graph Properties ⋮ Contemplations on Testing Graph Properties ⋮ Relational Properties Expressible with One Universal Quantifier Are Testable ⋮ Planar graphs: Random walks and bipartiteness testing ⋮ Testing the supermodular-cut condition
Cites Work
This page was built for publication: Testing the diameter of graphs
