Property Testing on k-Vertex-Connectivity of Graphs

DOI10.1007/978-3-540-70575-8_44MaRDI QIDQ3521945zbMATH OpenOpenAlexFDO

Authors Yuichi Yoshida, Hiro Ito

Publication date 28 August 2008

Published in Automata, Languages and Programming (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-540-70575-8_44

Mathematics Subject Classification ID

Connectivity (05C40) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Nonnumerical algorithms (68W05)

Recommendations

• Property testing on \(k\)-vertex-connectivity of graphs
• Testing \(k\)-edge-connectivity of digraphs
• Testing Eulerianity and connectivity in directed sparse graphs
• scientific article; zbMATH DE number 1559556
• Property testing in bounded degree graphs

Cited in

(9)

• Dynamic graph stream algorithms in \(o(n)\) space
• Property testing on \(k\)-vertex-connectivity of graphs
• Testing st-Connectivity
• Testing the \((s,t)\) connectivity of graphs and digraphs
• Testing connectivity of faulty networks in sublinear time
• Testing \(k\)-edge-connectivity of digraphs
• Computing and Testing Small Connectivity in Near-Linear Time and Queries via Fast Local Cut Algorithms
• A Combinatorial Characterization of the Testable Graph Properties: It's All About Regularity
• Testing Eulerianity and connectivity in directed sparse graphs

This page was built for publication: Property Testing on k-Vertex-Connectivity of Graphs

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