Testing Eulerianity and connectivity in directed sparse graphs

DOI10.1016/J.TCS.2011.06.038zbMATH Open1238.05110OpenAlexW2083280764MaRDI QIDQ653336FDOQ653336

Authors Yaron Orenstein, Dana Ron

Publication date 9 January 2012

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2011.06.038

zbMATH Keywords

property testingdecision problems

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20)

Recommendations

• Testing \(k\)-edge-connectivity of digraphs
• Property testing in bounded degree graphs
• Testing the \((s,t)\) connectivity of graphs and digraphs
• Property testing in sparse directed graphs: strong connectivity and subgraph-freeness
• On the query complexity of testing orientations for being Eulerian

Cites work

• scientific article; zbMATH DE number 1819631 (Why is no real title available?)
• scientific article; zbMATH DE number 5485551 (Why is no real title available?)
• scientific article; zbMATH DE number 1559556 (Why is no real title available?)
• scientific article; zbMATH DE number 1857651 (Why is no real title available?)
• scientific article; zbMATH DE number 6469238 (Why is no real title available?)
• A Characterization of the (Natural) Graph Properties Testable with One-Sided Error
• A Combinatorial Characterization of the Testable Graph Properties: It's All About Regularity
• A sublinear bipartiteness tester for bounded degree graphs
• An Expansion Tester for Bounded Degree Graphs
• Augmenting Graphs to Meet Edge-Connectivity Requirements
• Directed vertex-connectivity augmentation
• Edge-connectivity augmentation problems
• Efficient testing of large graphs
• Every Monotone Graph Property Is Testable
• Independence free graphs and vertex connectivity augmentation
• Local Graph Partitions for Approximation and Testing
• Minimal edge-coverings of pairs of sets
• On the Query Complexity of Testing Orientations for Being Eulerian
• Property Testing on k-Vertex-Connectivity of Graphs
• Property testing and its connection to learning and approximation
• Property testing in bounded degree graphs
• Robust Characterizations of Polynomials with Applications to Program Testing
• Testing Expansion in Bounded-Degree Graphs
• Testing \(k\)-edge-connectivity of digraphs
• Testing properties of directed graphs: acyclicity and connectivity*
• Testing subgraphs in directed graphs
• Testing the diameter of graphs
• Testing the expansion of a graph
• Testing versus Estimation of Graph Properties
• Tight Bounds for Testing Bipartiteness in General Graphs

Cited in

(17)

• On the characterization of 1-sided error strongly testable graph properties for bounded-degree graphs
• Testing whether the uniform distribution is a stationary distribution
• Constant-time algorithms for sparsity matroids
• Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
• Property testing on \(k\)-vertex-connectivity of graphs
• scientific article; zbMATH DE number 1670872 (Why is no real title available?)
• Relating two property testing models for bounded degree directed graphs
• Property testing in sparse directed graphs: strong connectivity and subgraph-freeness
• Testing uniformity of stationary distribution
• Property Testing on k-Vertex-Connectivity of Graphs
• Testing the supermodular-cut condition
• On the query complexity of testing orientations for being Eulerian
• Testing the \((s,t)\) connectivity of graphs and digraphs
• Testing the diameter of graphs
• Testing properties of directed graphs: acyclicity and connectivity*
• Dynamic graph stream algorithms in \(o(n)\) space
• Distribution-free connectivity testing for sparse graphs

This page was built for publication: Testing Eulerianity and connectivity in directed sparse graphs

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