math.CO

(what is this?)

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

Abstract: 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 strongly polynomial purely combinatorial algorithm to find such a packing.
 Comments: 25 pages, 10 figures Subjects: Combinatorics (math.CO) MSC classes: 90C27, 05C10, 05C12, 05C21, 05C85 Cite as: arXiv:1803.07020 [math.CO] (or arXiv:1803.07020v1 [math.CO] for this version)

Submission history

From: Alexander V. Karzanov [view email]
[v1] Mon, 19 Mar 2018 16:28:35 GMT (366kb)