Relating two property testing models for bounded degree directed graphs

DOI10.1145/2897518.2897575zbMath1376.68165OpenAlexW2418413199MaRDI QIDQ5361900

Pan Peng, Christian Sohler, Artur Czumaj

Publication date: 29 September 2017

Published in: Proceedings of the forty-eighth annual ACM symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/2897518.2897575

zbMATH Keywords

sampling-based algorithmsgraph property testingdirected graph algorithms

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Directed graphs (digraphs), tournaments (05C20) Randomized algorithms (68W20)

Related Items (4)

Property Testing for Bounded Degree Databases ⋮ Unnamed Item ⋮ On the characterization of 1-sided error strongly testable graph properties for bounded-degree graphs ⋮ An explicit construction of graphs of bounded degree that are far from being Hamiltonian

This page was built for publication: Relating two property testing models for bounded degree directed graphs