cicyt UNIZAR
Full-text links:

Download:

Current browse context:

math.CO

Change to browse by:

References & Citations

Bookmark

(what is this?)
CiteULike logo BibSonomy logo Mendeley logo del.icio.us logo Digg logo Reddit logo ScienceWISE logo

Mathematics > Combinatorics

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)