Testing st-Connectivity

DOI10.1007/978-3-540-74208-1_28MaRDI QIDQ3603479zbMATHOpenAlexFDO

Authors Sourav Chakraborty, Eldar Fischer, Oded Lachish, Arie Matsliah, Ilan Newman

Publication date 17 February 2009

Published in Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-540-74208-1_28

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Connectivity (05C40)

Recommendations

• Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
• Formal Techniques for Networked and Distributed Systems – FORTE 2004
• Connectivity testing
• Testing \(k\)-edge-connectivity of digraphs
• Testing connectivity of faulty networks in sublinear time
• scientific article; zbMATH DE number 3846725
• Efficient connectivity testing of hypercubic networks with faults
• Property testing on \(k\)-vertex-connectivity of graphs
• Property Testing on k-Vertex-Connectivity of Graphs

Cited in

(7)

• Testing whether the uniform distribution is a stationary distribution
• An algebraic characterization of testable Boolean CSPs
• Testing convexity properties of tree colorings
• Testing list \(H\)-homomorphisms
• Testing the \((s,t)\) connectivity of graphs and digraphs
• Property testing of massively parametrized problems -- a survey
• On the Query Complexity of Testing Orientations for Being Eulerian

This page was built for publication: Testing st-Connectivity

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