Relating two property testing models for bounded degree directed graphs

DOI10.1145/2897518.2897575zbMATH Open1376.68165OpenAlexW2418413199MaRDI QIDQ5361900FDOQ5361900

Authors 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

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

Recommendations

• Property testing in sparse directed graphs: strong connectivity and subgraph-freeness
• On the characterization of 1-sided error strongly testable graph properties for bounded-degree graphs
• Testing subgraphs in directed graphs
• Testing subgraphs in directed graphs
• Testing Eulerianity and connectivity in directed sparse graphs

Cited in

(5)

• On the characterization of 1-sided error strongly testable graph properties for bounded-degree graphs
• scientific article; zbMATH DE number 7758318 (Why is no real title available?)
• An explicit construction of graphs of bounded degree that are far from being Hamiltonian
• On testability of first-order properties in bounded-degree graphs and connections to proximity-oblivious testing
• Property testing for bounded degree databases

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5361900)