Testing Eulerianity and connectivity in directed sparse graphs

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

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)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• 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
• 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
• Testing Expansion in Bounded-Degree Graphs
• Local Graph Partitions for Approximation and Testing
• An Expansion Tester for Bounded Degree Graphs

Cited In (5)

• Title not available (Why is that?)
• Dynamic graph stream algorithms in \(o(n)\) space
• Testing the \((s,t)\) connectivity of graphs and digraphs
• Distribution-free connectivity testing for sparse graphs
• On the characterization of 1-sided error strongly testable graph properties for bounded-degree 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)