Distribution-free connectivity testing for sparse graphs

DOI10.1007/s00453-007-9054-1zbMath1138.68044OpenAlexW2046654297MaRDI QIDQ926283

Shirley Halevy, Eyal Kushilevitz

Publication date: 27 May 2008

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-007-9054-1

zbMATH Keywords

Property testingConnectivity testingDistribution-free testingProperties of sparse graphs

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Connectivity (05C40)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Testing juntas
• Self-testing/correcting with applications to numerical problems
• Spot-checkers
• Fast approximate PCPs for multidimensional bin-packing problems
• Testing hypergraph colorability
• Testing metric properties
• On the strength of comparisons in property testing
• Improved low-degree testing and its applications
• Regular Languages are Testable with a Constant Number of Queries
• On Testing Expansion in Bounded-Degree Graphs
• Testing Membership in Languages that Have Small Width Branching Programs
• Property testing and its connection to learning and approximation
• Monotonicity testing over general poset domains
• Every monotone graph property is testable
• Testing triangle-freeness in general graphs
• On the Robustness of Functional Equations
• Three theorems regarding testing graph properties
• Testing satisfiability
• Testing of Clustering
• Testing the diameter of graphs
• Tight Bounds for Testing Bipartiteness in General Graphs
• Testing membership in parenthesis languages
• Robust Characterizations of Polynomials with Applications to Program Testing
• Testing of matrix properties
• Automata, Languages and Programming
• Approximation, Randomization, and Combinatorial Optimization.. Algorithms and Techniques
• Approximation, Randomization, and Combinatorial Optimization.. Algorithms and Techniques
• Testing subgraphs in directed graphs
• Testing monotonicity
• Efficient testing of large graphs
• Property testing in bounded degree graphs