Testing st-Connectivity

DOI10.1007/978-3-540-74208-1_28zbMATH Open1171.68597OpenAlexW1880824757MaRDI QIDQ3603479FDOQ3603479

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

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
• Efficient connectivity testing of hypercubic networks with faults
• Property testing on \(k\)-vertex-connectivity of graphs
• Property Testing on k-Vertex-Connectivity of Graphs

Mathematics Subject Classification ID

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

Cited In (7)

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

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)