Testing st-Connectivity

DOI10.1007/978-3-540-74208-1_28MaRDI QIDQ3603479zbMATH OpenOpenAlexFDO

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

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

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

(8)

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

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)