Testing the supermodular-cut condition

DOI10.1007/s00453-013-9842-8zbMath1325.68171OpenAlexW1997480274MaRDI QIDQ2350909

Yuichi Yoshida, Shin-ichi Tanigawa

Publication date: 25 June 2015

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-013-9842-8

zbMATH Keywords

supermodularityproperty testingbounded-degree model

Mathematics Subject Classification ID

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

Cites Work

• Unnamed Item
• Testing \(k\)-edge-connectivity of digraphs
• Covering symmetric supermodular functions by graphs
• Property testing on \(k\)-vertex-connectivity of graphs
• Constant-Time Algorithms for Sparsity Matroids
• A Survey on Covering Supermodular Functions
• Property testing and its connection to learning and approximation
• Testing the diameter of graphs
• Tight Bounds for Testing Bipartiteness in General Graphs
• Property testing in bounded degree graphs