License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/OASIcs.ATMOS.2015.56
URN: urn:nbn:de:0030-drops-54611
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2015/5461/
Go to the corresponding OASIcs Volume Portal

Takaoka, Tadao

Single Source Shortest Paths for All Flows with Integer Costs

pdf-format:
12.pdf (0.4 MB)

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.

BibTeX - Entry

@InProceedings{takaoka:OASIcs:2015:5461,
  author =	{Tadao Takaoka},
  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 =	{OpenAccess Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-99-6},
  ISSN =	{2190-6807},
  year =	{2015},
  volume =	{48},
  editor =	{Giuseppe F. Italiano and Marie Schmidt},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2015/5461},
  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}
}

Keywords: information sharing, shortest path problem for all flows, priority queue, limited edge cost, transportation network
Collection: 15th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2015)
Issue Date: 2015
Date of publication: 14.09.2015

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI