Efficient algorithms for minimum range cut problems
Naoki Katoh, Kazuo Iwano · Networks · 1994
Abstract LetG = (V, E)be an undirected graph withnvertices andmedges such that a real‐valued weight, denoted byw(e), is associated with each edgee. This paper studies what we call the minimum range cut problem that asks to find a cut inGsuch that the range of all edge weights in the cut is minimum. Here, the range of a cutCis defined to be the maximum difference among weights of edges in the cut, i.e., maxeϵcw(e)‐ mineϵcw(e). This paper proposes anO(m + nlogn) algorithm for the minimum range cut problem. It is also shown that this running time is optimal. We also study two variants of this problem. One is the minimum range target cut problem. Given a prespecified value called a target, this problem asks to find a cut with minimum range among all cuts such that the target value is between the minimum and maximum of weights of edges in the cut. The second is the minimum ranges – tcut problem that asks to find ans – tcut with minimum range. This paper proposesO(m + nlogn) algorithms for these problems. For the second problem, we show that anancestor treeofO(n)space recently developed by Cheng and Hu effectively represents all pairs minimum range cuts, which can be constructed inO(n2)time, and enables us to answer any minimum ranges – tcut query inO(1)time [resp., inO(n)time] if we want to obtain only the range value of the cut (resp., the bipartition of vertices induced by the cut). © 1994 by John Wiley & Sons, Inc.