Testing the diameter of graphs
From MaRDI portal
Recommendations
Cites work
Cited in
(40)- Relational Properties Expressible with One Universal Quantifier Are Testable
- scientific article; zbMATH DE number 1418268 (Why is no real title available?)
- Testing convexity properties of tree colorings
- scientific article; zbMATH DE number 1222089 (Why is no real title available?)
- Contemplations on Testing Graph Properties
- Testing \(k\)-edge-connectivity of digraphs
- Dynamic graph stream algorithms in \(o(n)\) space
- Local reconstructors and tolerant testers for connectivity and diameter
- Testing Eulerianity and connectivity in directed sparse graphs
- Comparing the strength of query types in property testing: the case of testing \(k\)-colorability
- Testing the supermodular-cut condition
- Planar graphs: random walks and bipartiteness testing
- Testing the \((s,t)\) connectivity of graphs and digraphs
- Testable and untestable classes of first-order formulae
- On sampling edges almost uniformly
- On approximating the number of relevant variables in a function
- Erasure-resilient sublinear-time graph algorithms
- The subgraph testing model
- Introduction to testing graph properties
- A separation theorem in property testing
- Testing triangle freeness in the general model in graphs with arboricity \(O(\sqrt{n})\)
- Introduction to testing graph properties
- Testing connectedness of images
- Lower bounds for approximating graph parameters via communication complexity
- On the Communication Complexity Methodology for Proving Lower Bounds on the Query Complexity of Property Testing
- Testing Expansion in Bounded-Degree Graphs
- Testing some first-order logic properties on sparse graphs
- Testing Euclidean Spanners
- Testing C_k-freeness in bounded-arboricity graphs
- Testing isomorphism in the bounded-degree graph model
- Finding cycles and trees in sublinear time
- Comparing the strength of query types in property testing: the case of \(k\)-colorability
- Testing outerplanarity of bounded degree graphs
- scientific article; zbMATH DE number 7758318 (Why is no real title available?)
- Distribution-free connectivity testing for sparse graphs
- On the characterization of 1-sided error strongly testable graph properties for bounded-degree graphs
- Every minor-closed property of sparse graphs is testable
- On the Query Complexity of Testing Orientations for Being Eulerian
- Shortcutting directed and undirected networks with a degree constraint
- Flexible Models for Testing Graph Properties
This page was built for publication: Testing the diameter of graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4543626)
