Skip to main content
eScholarship
Open Access Publications from the University of California

Minimum range balanced cuts via dynamic subset sums

  • Author(s): Eppstein, David
  • et al.
Abstract

We find the balanced cut in a graph that minimizes the maximum difference between edge lengths, in time O(m + n^2 log n), improving a previous O(m + n^2.5) bound. We use subroutines for solving a dynamic subset sum problem, in time O(l log l log n) per operation in the fully dynamic setting, or in time O(l log n) per operation in the semi-online setting in which one can predict a superset of future deletions.

Main Content
Current View