License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICALP.2018.44
URN: urn:nbn:de:0030-drops-90487
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/9048/
Go to the corresponding LIPIcs Volume Portal

Duan, Ran ; Gu, Yong ; Zhang, Le

Improved Time Bounds for All Pairs Non-decreasing Paths in General Digraphs

pdf-format:
LIPIcs-ICALP-2018-44.pdf (0.5 MB)

Abstract

We present improved algorithms for solving the All Pairs Non-decreasing Paths (APNP) problem on weighted digraphs. Currently, the best upper bound on APNP is O~(n^{(9+omega)/4})=O(n^{2.844}), obtained by Vassilevska Williams [TALG 2010 and SODA'08], where omega<2.373 is the usual exponent of matrix multiplication. Our first algorithm improves the time bound to O~(n^{2+omega/3})=O(n^{2.791}). The algorithm determines, for every pair of vertices s, t, the minimum last edge weight on a non-decreasing path from s to t, where a non-decreasing path is a path on which the edge weights form a non-decreasing sequence. The algorithm proposed uses the combinatorial properties of non-decreasing paths. Also a slightly improved algorithm with running time O(n^{2.78}) is presented.

BibTeX - Entry

@InProceedings{duan_et_al:LIPIcs:2018:9048,
  author =	{Ran Duan and Yong Gu and Le Zhang},
  title =	{{Improved Time Bounds for All Pairs Non-decreasing Paths in General Digraphs}},
  booktitle =	{45th International Colloquium on Automata, Languages, and  Programming (ICALP 2018)},
  pages =	{44:1--44:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-076-7},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{107},
  editor =	{Ioannis Chatzigiannakis and Christos Kaklamanis and D{\'a}niel Marx and Donald Sannella},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/9048},
  URN =		{urn:nbn:de:0030-drops-90487},
  doi =		{10.4230/LIPIcs.ICALP.2018.44},
  annote =	{Keywords: Graph algorithms, Matrix multiplication, Non-decreasing paths}
}

Keywords: Graph algorithms, Matrix multiplication, Non-decreasing paths
Collection: 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)
Issue Date: 2018
Date of publication: 04.07.2018

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