Testing the \((s,t)\) connectivity of graphs and digraphs

DOI10.1016/j.tcs.2012.01.045zbMath1242.68367OpenAlexW2054991524MaRDI QIDQ428880

Yusuke Kobayashi, Yuichi Yoshida

Publication date: 25 June 2012

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2012.01.045

zbMATH Keywords

property testingbounded-degree modeldisconnectivitygeneral graph modelHorn SAT

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Connectivity (05C40) Randomized algorithms (68W20)

Related Items (1)

Testing list \(H\)-homomorphisms

Cites Work

• Unnamed Item
• Unnamed Item
• Testing \(k\)-edge-connectivity of digraphs
• The electrical resistance of a graph captures its commute and cover times
• 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
• Testing triangle-freeness in general graphs
• A Chernoff Bound for Random Walks on Expander Graphs
• Testing the diameter of graphs
• Tight Bounds for Testing Bipartiteness in General Graphs
• Introduction to Testing Graph Properties
• lgorithmic and Analysis Techniques in Property Testing
• Optimal constant-time approximation algorithms and (unconditional) inapproximability results for every bounded-degree CSP
• Property testing in bounded degree graphs

This page was built for publication: Testing the \((s,t)\) connectivity of graphs and digraphs