Testing Eulerianity and connectivity in directed sparse graphs
From MaRDI portal
Publication:653336
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
Recommendations
Cites Work
- Testing subgraphs in directed graphs
- Property testing and its connection to learning and approximation
- Efficient testing of large graphs
- Property testing in bounded degree graphs
- On the Query Complexity of Testing Orientations for Being Eulerian
- Robust Characterizations of Polynomials with Applications to Program Testing
- Augmenting Graphs to Meet Edge-Connectivity Requirements
- A Combinatorial Characterization of the Testable Graph Properties: It's All About Regularity
- A sublinear bipartiteness tester for bounded degree graphs
- Every Monotone Graph Property Is Testable
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Minimal edge-coverings of pairs of sets
- Testing the expansion of a graph
- Directed vertex-connectivity augmentation
- Independence free graphs and vertex connectivity augmentation
- Property Testing on k-Vertex-Connectivity of Graphs
- Testing the diameter of graphs
- Testing properties of directed graphs: acyclicity and connectivity*
- Tight Bounds for Testing Bipartiteness in General Graphs
- Testing \(k\)-edge-connectivity of digraphs
- A Characterization of the (Natural) Graph Properties Testable with One-Sided Error
- Edge-connectivity augmentation problems
- Testing versus Estimation of Graph Properties
- Title not available (Why is that?)
- Testing Expansion in Bounded-Degree Graphs
- Local Graph Partitions for Approximation and Testing
- An Expansion Tester for Bounded Degree Graphs
Cited In (11)
- Testing the diameter of graphs
- Testing properties of directed graphs: acyclicity and connectivity*
- Title not available (Why is that?)
- Dynamic graph stream algorithms in \(o(n)\) space
- Testing the \((s,t)\) connectivity of graphs and digraphs
- Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
- Property testing on \(k\)-vertex-connectivity of graphs
- Distribution-free connectivity testing for sparse graphs
- On the characterization of 1-sided error strongly testable graph properties for bounded-degree graphs
- Property Testing on k-Vertex-Connectivity of Graphs
- Property testing in sparse directed graphs: strong connectivity and subgraph-freeness
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)
