English
 
User Manual Privacy Policy Disclaimer Contact us
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT
  Improved Algorithms for Computing the Cycle of Minimum Cost-to-Time Ratio in Directed Graphs

Bringmann, K., Dueholm Hansen, T., & Krinninger, S. (2017). Improved Algorithms for Computing the Cycle of Minimum Cost-to-Time Ratio in Directed Graphs. Retrieved from http://arxiv.org/abs/1704.08122.

Item is

Basic

show hide
Item Permalink: http://hdl.handle.net/11858/00-001M-0000-002D-89BC-3 Version Permalink: http://hdl.handle.net/11858/00-001M-0000-002D-89BD-1
Genre: Paper

Files

show Files
hide Files
:
arXiv:1704.08122.pdf (Preprint), 725KB
Name:
arXiv:1704.08122.pdf
Description:
File downloaded from arXiv at 2017-07-04 11:36 Accepted to the 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)
Visibility:
Public
MIME-Type / Checksum:
application/pdf / [MD5]
Technical Metadata:
Copyright Date:
-
Copyright Info:
-

Locators

show

Creators

show
hide
 Creators:
Bringmann, Karl1, Author              
Dueholm Hansen, Thomas2, Author
Krinninger, Sebastian2, Author              
Affiliations:
1Algorithms and Complexity, MPI for Informatics, Max Planck Society, ou_24019              
2External Organizations, ou_persistent22              

Content

show
hide
Free keywords: Computer Science, Data Structures and Algorithms, cs.DS
 Abstract: We study the problem of finding the cycle of minimum cost-to-time ratio in a directed graph with $ n $ nodes and $ m $ edges. This problem has a long history in combinatorial optimization and has recently seen interesting applications in the context of quantitative verification. We focus on strongly polynomial algorithms to cover the use-case where the weights are relatively large compared to the size of the graph. Our main result is an algorithm with running time $ \tilde O (m^{3/4} n^{3/2}) $, which gives the first improvement over Megiddo's $ \tilde O (n^3) $ algorithm [JACM'83] for sparse graphs. We further demonstrate how to obtain both an algorithm with running time $ n^3 / 2^{\Omega{(\sqrt{\log n})}} $ on general graphs and an algorithm with running time $ \tilde O (n) $ on constant treewidth graphs. To obtain our main result, we develop a parallel algorithm for negative cycle detection and single-source shortest paths that might be of independent interest.

Details

show
hide
Language(s): eng - English
 Dates: 2017-04-262017
 Publication Status: Published online
 Pages: 19 p.
 Publishing info: -
 Table of Contents: -
 Rev. Method: -
 Identifiers: arXiv: 1704.08122
URI: http://arxiv.org/abs/1704.08122
BibTex Citekey: DBLP:journals/corr/BringmannHK17
 Degree: -

Event

show

Legal Case

show

Project information

show

Source

show