Testing properties of directed graphs: acyclicity and connectivity*

DOI10.1002/rsa.10023zbMath1002.68113OpenAlexW4251780626MaRDI QIDQ4543627

Dana Ron, Michael A. Bender

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.10023

zbMATH Keywords

strong connectivitysparse graphs

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Graph representations (geometric and intersection representations, etc.) (05C62)

Related Items (12)

Property Testing for Bounded Degree Databases ⋮ Introduction to Testing Graph Properties ⋮ Testing Eulerianity and connectivity in directed sparse graphs ⋮ Testing \(k\)-edge-connectivity of digraphs ⋮ On the Query Complexity of Testing Orientations for Being Eulerian ⋮ Testing Expansion in Bounded-Degree Graphs ⋮ Testing hypergraph colorability ⋮ Property Testing of Massively Parametrized Problems – A Survey ⋮ Fast distributed algorithms for testing graph properties ⋮ 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

Cites Work

• Unnamed Item
• Property testing and its connection to learning and approximation
• Probabilistic checking of proofs
• Interactive proofs and the hardness of approximating cliques

This page was built for publication: Testing properties of directed graphs: acyclicity and connectivity*