 License: Creative Commons Attribution 3.0 Unported license (CC-BY 3.0)
when quoting this document, please refer to the following
DOI:
URN: urn:nbn:de:0030-drops-82750
URL:

;

### Faster Algorithms for Half-Integral T-Path Packing

 pdf-format:

### Abstract

Let G = (V, E) be an undirected graph, a subset of vertices T be a set of terminals. Then a natural combinatorial problem consists in finding the maximum number of vertex-disjoint paths connecting distinct terminals. For this problem, a clever construction suggested by Gallai reduces it to computing a maximum non-bipartite matching and thus gives an O(mn^1/2 log(n^2/m)/log(n))-time algorithm (hereinafter n := |V|, m := |E|). Now let us consider the fractional relaxation, i.e. allow T-path packings with arbitrary nonnegative real weights. It is known that there always exists a half-integral solution, that is, one only needs to assign weights 0, 1/2, 1 to maximize the total weight of T-paths. It is also known that an optimum half-integral packing can be found in strongly-polynomial time but the actual time bounds are far from being satisfactory. In this paper we present a novel algorithm that solves the half-integral problem within O(mn^1/2 log(n^2/m)/log(n)) time, thus matching the complexities of integral and half-integral versions.

### BibTeX - Entry

```@InProceedings{babenko_et_al:LIPIcs:2017:8275,
author =	{Maxim Babenko and Stepan Artamonov},
title =	{{Faster Algorithms for Half-Integral T-Path Packing}},
booktitle =	{28th International Symposium on Algorithms and Computation (ISAAC 2017)},
pages =	{8:1--8:12},
series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN =	{978-3-95977-054-5},
ISSN =	{1868-8969},
year =	{2017},
volume =	{92},
editor =	{Yoshio Okamoto and Takeshi Tokuyama},
publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address =	{Dagstuhl, Germany},
URL =		{http://drops.dagstuhl.de/opus/volltexte/2017/8275},
URN =		{urn:nbn:de:0030-drops-82750},
doi =		{10.4230/LIPIcs.ISAAC.2017.8},
annote =	{Keywords: graph algorithms, multiflows, path packings, matchings}
}
```

 Keywords: graph algorithms, multiflows, path packings, matchings Seminar: 28th International Symposium on Algorithms and Computation (ISAAC 2017) Issue date: 2017 Date of publication: 07.12.2017

DROPS-Home | Fulltext Search | Imprint | Privacy 