Property testing on \(k\)-vertex-connectivity of graphs

DOI10.1007/s00453-010-9477-yzbMath1239.05112OpenAlexW2022140055MaRDI QIDQ2428696

Hiro Ito, Yuichi Yoshida

Publication date: 26 April 2012

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-010-9477-y

zbMATH Keywords

vertex connectivityproperty testing

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Connectivity (05C40)

Related Items

On the tree-width of even-hole-free graphs, Testing outerplanarity of bounded degree graphs, An explicit construction of graphs of bounded degree that are far from being Hamiltonian, Testing the supermodular-cut condition

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Testing \(k\)-edge-connectivity of digraphs
• A note on the vertex-connectivity augmentation problem
• Independence free graphs and vertex connectivity augmentation
• On the optimal vertex-connectivity augmentation
• On Testing Expansion in Bounded-Degree Graphs
• Property testing and its connection to learning and approximation
• On the Structure of Minimum-Weight k-Connected Spanning Networks
• Robust Characterizations of Polynomials with Applications to Program Testing
• On rooted node-connectivity problems