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

DOI10.1016/J.TCS.2012.01.045zbMATH Open1242.68367OpenAlexW2054991524MaRDI QIDQ428880FDOQ428880

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

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

zbMATH Keywords

property testingbounded-degree modeldisconnectivitygeneral graph modelHorn SAT

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (6)

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

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)