1 Search Results for "Artamonov, Stepan"

Document
DOI: 10.4230/LIPIcs.ISAAC.2017.8
Faster Algorithms for Half-Integral T-Path Packing

Authors: Maxim Babenko and Stepan Artamonov

Published in: LIPIcs, Volume 92, 28th International Symposium on Algorithms and Computation (ISAAC 2017)

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.
Cite as

Maxim Babenko and Stepan Artamonov. Faster Algorithms for Half-Integral T-Path Packing. In 28th International Symposium on Algorithms and Computation (ISAAC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 92, pp. 8:1-8:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{babenko_et_al:LIPIcs.ISAAC.2017.8,
  author =	{Babenko, Maxim and Artamonov, Stepan},
  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 =	{Okamoto, Yoshio and Tokuyama, Takeshi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2017.8},
  URN =		{urn:nbn:de:0030-drops-82750},
  doi =		{10.4230/LIPIcs.ISAAC.2017.8},
  annote =	{Keywords: graph algorithms, multiflows, path packings, matchings}
}
  • Refine by Author
  • 1 Artamonov, Stepan
  • 1 Babenko, Maxim

  • Refine by Classification

  • Refine by Keyword
  • 1 graph algorithms
  • 1 matchings
  • 1 multiflows
  • 1 path packings

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2017

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact