Testing Eulerianity and connectivity in directed sparse graphs
From MaRDI portal
Publication:653336
DOI10.1016/j.tcs.2011.06.038zbMath1238.05110OpenAlexW2083280764MaRDI QIDQ653336
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
Related Items
Dynamic graph stream algorithms in \(o(n)\) space, On the characterization of 1-sided error strongly testable graph properties for bounded-degree graphs
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Testing \(k\)-edge-connectivity of digraphs
- Testing the expansion of a graph
- Edge-connectivity augmentation problems
- Directed vertex-connectivity augmentation
- Independence free graphs and vertex connectivity augmentation
- Minimal edge-coverings of pairs of sets
- A sublinear bipartiteness tester for bounded degree graphs
- Property testing and its connection to learning and approximation
- Property Testing on k-Vertex-Connectivity of Graphs
- On the Query Complexity of Testing Orientations for Being Eulerian
- A Characterization of the (Natural) Graph Properties Testable with One-Sided Error
- Every Monotone Graph Property Is Testable
- Augmenting Graphs to Meet Edge-Connectivity Requirements
- Testing the diameter of graphs
- Testing properties of directed graphs: acyclicity and connectivity*
- Tight Bounds for Testing Bipartiteness in General Graphs
- Robust Characterizations of Polynomials with Applications to Program Testing
- Testing Expansion in Bounded-Degree Graphs
- Local Graph Partitions for Approximation and Testing
- A Combinatorial Characterization of the Testable Graph Properties: It's All About Regularity
- Testing versus Estimation of Graph Properties
- An Expansion Tester for Bounded Degree Graphs
- Testing subgraphs in directed graphs
- Efficient testing of large graphs
- Property testing in bounded degree graphs
