A Simple Framework for Finding Balanced Sparse Cuts via APSP
We present a very simple and intuitive algorithm to find balanced sparse cuts in a graph via shortest-paths. Our algorithm combines a new multiplicative-weights framework for solving unit-weight multi-commodity flows with standard ball growing arguments. Using Dijkstra's algorithm for computing the...
Đã lưu trong:
| Những tác giả chính: | , , , |
|---|---|
| Định dạng: | Bài viết |
| Được phát hành: |
2022
|
| Những chủ đề: | |
| Truy cập trực tuyến: | https://arxiv.org/abs/2209.08845 http://arxiv.org/abs/2209.08845 |
| Các nhãn: |
Không có thẻ, Là người đầu tiên thẻ bản ghi này!
|