A combinatorial algorithm for the minimum \((2,r)\)-metric problem and some generalizations
type: Item
instance of: scholarly article
title: A combinatorial algorithm for the minimum \((2,r)\)-metric problem and some generalizations
zbMATH Open document ID: 0924.90126
author: Alexander V. Karzanov
published in: Combinatorica
publication date: 1999-09-14T00:00:00Z
review text: A graph \(G(V,E)\) is given with nonnegative integer capacities \(c(e)\) on the edges \(e\in E\) and with a metric \(\mu\) establishing distances between pairs of vertices of \(T\subseteq V\). This metric should be extended to a (semi-)metric \(m\) on \(V\) so that \(m=\mu\) within \(T\), each \(x\in V\) is at zero distance from some \(t\in T\), and \(\sum_{e\in E} c(e)m(e)\) be as small as possible. This is the classical undirected cut problem for \(T=\{s,t\}\). Another special case is if \(\mu\) is the path metric (minimum number of edges in a path connecting the vertices) in the complete bipartite graph \(K_{2,r}\). This latter problem is polynomial but previous solutions used the ellipsoid method. The author gives a ``purely combinatorial'' method for this and for a certain associated integer multiflow problem.
reviewed by: András Recski
Mathematics Subject Classification ID: 90C35
Mathematics Subject Classification ID: 90B10
Mathematics Subject Classification ID: 90C27
zbMATH DE Number: 1336284
zbMATH Keywords: minimum \((2,r)\)-metric problem
MaRDI profile type: Publication
full work available at URL: s004930050040
OpenAlex ID: W2086358569
DOI: 10.1007/S004930050040
description: scientific article; zbMATH DE number 1336284