arXiv preprint ·
All minimum cuts of symmetric submodular functions
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
Abstract
We compute Cunningham's canonical decomposition of a symmetric submodular function on $n$ elements in $O(n^3)$ time. The decomposition represents all minimum cuts in linear space. For the pair $s,t$ produced by Queyranne's algorithm, we construct in $O(n^2)$ time a digraph representing exactly the minimum $st$-cuts of the function. Using this construction in Chekuri and Xu's decomposition algorithm gives the cubic bound.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Data Structures & Algorithms
A Universal Threshold Theory for Local Properties of Random Linear Codes
First-Order Model Checking on Monadically Dependent Graph Classes
The probabilistic bound for perfect hashing is sharp only for binary alphabets
Tusnády's problem and online two-sample thinning
A Complete Characterization of $q$-Ary $2$-Designs in Doubly-Extended Reed-Solomon Codes
Get the few papers worth your time in Data Structures & Algorithms every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.