• A
  • A
  • A
  • ABC
  • ABC
  • ABC
  • А
  • А
  • А
  • А
  • А
Regular version of the site

Article

An Improved Algorithm for Packing T-Paths in Inner Eulerian Networks

Lecture Notes in Computer Science. 2012. No. 7434. P. 109-120.
Babenko M. A., Artamonov S. I., Salikhov K.

A digraph G = (V,E) with a distinguished set T V of terminals is called inner Eulerian if for each v V T the numbers of arcs entering and leaving v are equal. By a T-path we mean a simple directed path connecting distinct terminals with all intermediate nodes in V T. This paper concerns the problem of finding a maximum T-path packing, i.e. a maximum collection of arc-disjoint T-paths. A min-max relation for this problem was established by Lomonosov. The capacitated version was studied by Ibaraki,  Karzanov, and Nagamochi, who came up with a strongly-polynomial algorithm of complexity O(φ(V,E) log T +V 2E) (hereinafter φ(n,m) denotes the complexity of a max-flow computation in a network with n nodes and m arcs). For unit capacities, the latter algorithm takes O(φ(V,E) log T +V E) time, which is unsatisfactory since a max-flow can be found in o(V E) time. For this case, we present an improved method that runs in O(φ(V,E) log T + E log V ) time. Thus plugging in the max-flow algorithm of Dinic, we reduce the overall complexity from O(V E) to O(min(V 2/3E,E3/2) log T).