An efficient algorithm for packing cuts and (2,3)-metrics in a planar graph with three holes

摘要

We consider a planar graph G in which the edges have nonnegative integer lengths such that the length of every cycle of G is even, and three faces are distinguished, called holes in G. It is known that there exists a packing of cuts and (2,3)-metrics with nonnegative integer weights in G which realizes the distances within each hole. We develop a purely combinatorial strongly polynomial-time algorithm to find such a packing. (C) 2019 Elsevier B.V. All rights reserved.