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

DOI10.1016/J.DISOPT.2019.04.002zbMATH Open1474.90379arXiv1803.07020OpenAlexW2963342999WikidataQ127984736 ScholiaQ127984736MaRDI QIDQ2010919FDOQ2010919

Authors: Alexander V. Karzanov 

Publication date: 28 November 2019

Published in: Discrete Optimization (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/1803.07020

Recommendations

• Paths and metrics in a planar graph with three or more holes. I: Metrics
• Distances and cuts in planar graphs
• Paths and metrics in a planar graph with three or more holes. II: Paths
• A combinatorial algorithm for the planar multiflow problem with demands located on three holes
• Packings of cuts realizing distances between certain vertices in a planar graph

zbMATH Keywords

shortest pathcutplanar graphpacking problem\((2,3)\)-metricstrongly polynomial-time algorithm

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Combinatorial optimization (90C27) Planar graphs; geometric and topological aspects of graph theory (05C10) Distance in graphs (05C12) Flows in graphs (05C21)

Cites Work

• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Multicommodity flows in planar graphs
• Multicommodity flows in graphs
• Sums of cuts and bipartite metrics
• On fractional multicommodity flows and distance functions
• Distances and cuts in planar graphs
• Packings of cuts realizing distances between certain vertices in a planar graph
• Paths and metrics in a planar graph with three or more holes. I: Metrics
• Paths and metrics in a planar graph with three or more holes. II: Paths

Cited In (3)

• Paths and metrics in a planar graph with three or more holes. I: Metrics
• Paths and metrics in a planar graph with three or more holes. II: Paths
• An $O ( | V |^2 )$ Algorithm for the Planar 3-Cut Problem

This page was built for publication: An efficient algorithm for packing cuts and \((2,3)\)-metrics in a planar graph with three holes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2010919)