DROPS

Document

DOI: 10.4230/OASIcs.ATMOS.2015.56

Single Source Shortest Paths for All Flows with Integer Costs

Authors: Tadao Takaoka

Published in: OASIcs, Volume 48, 15th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2015)

Abstract

We consider a shortest path problem for a directed graph with edges labeled with a cost and a capacity. The problem is to push an unsplittable flow $f$ from a specified source to all other vertices with the minimum cost for all f values. Let G = (V, E) with |V| = n and |E| = m. If there are t different capacity values, we can solve the single source shortest path problem t times for all f in O(tm + tn log n) time, which is O(m^2) when t = m. We improve this time to O(min{t, cn}m + cn^2), which is less than O(cmn) if edge costs are non-negative integers bounded by c. Our algorithm performs better for denser graphs.

Cite as

Tadao Takaoka. Single Source Shortest Paths for All Flows with Integer Costs. In 15th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2015). Open Access Series in Informatics (OASIcs), Volume 48, pp. 56-67, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{takaoka:OASIcs.ATMOS.2015.56,
  author =	{Takaoka, Tadao},
  title =	{{Single Source Shortest Paths for All Flows with Integer Costs}},
  booktitle =	{15th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2015)},
  pages =	{56--67},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-99-6},
  ISSN =	{2190-6807},
  year =	{2015},
  volume =	{48},
  editor =	{Italiano, Giuseppe F. and Schmidt, Marie},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2015.56},
  URN =		{urn:nbn:de:0030-drops-54611},
  doi =		{10.4230/OASIcs.ATMOS.2015.56},
  annote =	{Keywords: information sharing, shortest path problem for all flows, priority queue, limited edge cost, transportation network}
}

Search Results

Documents authored by Takaoka, Tadao

Single Source Shortest Paths for All Flows with Integer Costs

Abstract

Cite as

Thanks for your feedback!

Could not send message