Testing Eulerianity and connectivity in directed sparse graphs
type: Item
instance of: scholarly article
title: Testing Eulerianity and connectivity in directed sparse graphs
zbMATH Open document ID: 1238.05110
author: Yaron Orenstein
author: Dana Ron
published in: Theoretical Computer Science
publication date: 2012-01-09T00:00:00Z
Mathematics Subject Classification ID: 05C20
zbMATH DE Number: 5995831
zbMATH Keywords: property testing
zbMATH Keywords: decision problems
MaRDI profile type: Publication
full work available at URL: j.tcs.2011.06.038
OpenAlex ID: W2083280764
cites work: Efficient testing of large graphs
cites work: A Combinatorial Characterization of the Testable Graph Properties: It's All About Regularity
cites work: Testing subgraphs in directed graphs
cites work: Q5501357
cites work: A Characterization of the (Natural) Graph Properties Testable with One-Sided Error
cites work: Every Monotone Graph Property Is Testable
cites work: Testing properties of directed graphs: acyclicity and connectivity*
cites work: Q3549723
cites work: Testing Expansion in Bounded-Degree Graphs
cites work: Q3152421
cites work: Minimal edge-coverings of pairs of sets
cites work: Directed vertex-connectivity augmentation
cites work: On the Query Complexity of Testing Orientations for Being Eulerian
cites work: Testing versus Estimation of Graph Properties
cites work: Augmenting Graphs to Meet Edge-Connectivity Requirements
cites work: Property testing and its connection to learning and approximation
cites work: Q4527008
cites work: A sublinear bipartiteness tester for bounded degree graphs
cites work: Property testing in bounded degree graphs
cites work: Local Graph Partitions for Approximation and Testing
cites work: Independence free graphs and vertex connectivity augmentation
cites work: Tight Bounds for Testing Bipartiteness in General Graphs
cites work: An Expansion Tester for Bounded Degree Graphs
cites work: Testing the expansion of a graph
cites work: Testing the diameter of graphs
cites work: Q4788610
cites work: Robust Characterizations of Polynomials with Applications to Program Testing
cites work: Edge-connectivity augmentation problems
cites work: Property Testing on k-Vertex-Connectivity of Graphs
cites work: Testing \(k\)-edge-connectivity of digraphs
DOI: 10.1016/J.TCS.2011.06.038
description: scientific article; zbMATH DE number 5995831