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

DOI10.1016/J.TCS.2012.01.045MaRDI QIDQ428880zbMATHOpenAlexFDO

Authors Yuichi Yoshida, Yusuke Kobayashi

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) Randomized algorithms (68W20) Connectivity (05C40)

Recommendations

• Testing \(k\)-edge-connectivity of digraphs
• Testing 2-vertex connectivity and computing pairs of vertex-disjoint \(s\)-\(t\) paths in digraphs
• Property testing on \(k\)-vertex-connectivity of graphs
• Property Testing on k-Vertex-Connectivity of Graphs
• On testing single connectedness in directed graphs and some related problems
• Directed \(s\)-\(t\) numberings, rubber bands, and testing digraph \(k\)-vertex connecitivity
• Testing Eulerianity and connectivity in directed sparse graphs
• Testing properties of directed graphs: acyclicity and connectivity*
• Testing st-Connectivity
• scientific article; zbMATH DE number 742980

Cites work

• scientific article; zbMATH DE number 1670872 (Why is no real title available?)
• scientific article; zbMATH DE number 5605086 (Why is no real title available?)
• A Chernoff Bound for Random Walks on Expander Graphs
• A sublinear bipartiteness tester for bounded degree graphs
• Algorithmic and analysis techniques in property testing
• Introduction to testing graph properties
• Optimal constant-time approximation algorithms and (unconditional) inapproximability results for every bounded-degree CSP
• Property Testing on k-Vertex-Connectivity of Graphs
• Property testing and its connection to learning and approximation
• Property testing in bounded degree graphs
• Testing \(k\)-edge-connectivity of digraphs
• Testing the diameter of graphs
• Testing triangle-freeness in general graphs
• The electrical resistance of a graph captures its commute and cover times
• Tight Bounds for Testing Bipartiteness in General Graphs

Cited in

(8)

• Local reconstructors and tolerant testers for connectivity and diameter
• Testing list \(H\)-homomorphisms
• A Combinatorial Characterization of the Testable Graph Properties: It's All About Regularity
• Testing \(k\)-edge-connectivity of digraphs
• Testing the supermodular-cut condition
• Testing Eulerianity and connectivity in directed sparse graphs
• Testing properties of directed graphs: acyclicity and connectivity*
• On one test for the switching separability of graphs modulo \(q\)

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q428880)