Randomized algorithms for finding the shortest negative cost cycle in networks
In this paper, we design and analyze a fast, randomized algorithm for the problem of finding a negative cost cycle having the smallest number of edges in a directed, weighted graph. This problem will henceforth be referred to as the Shortest Negative Cost Cycle problem (SNCC). SNCC is closely relate...
Main Authors: | Orlin, James B, Subramani, K., Wojciechowki, Piotr |
---|---|
Other Authors: | Sloan School of Management |
Format: | Article |
Language: | English |
Published: |
Elsevier BV
2020
|
Online Access: | https://hdl.handle.net/1721.1/125248 |
Similar Items
-
Improved primal simplex algorithms for shortest path, assignment and minimum cost flow problems
by: Ahuja, Ravindra K., et al.
Published: (2009) -
A Faster Algorithm for the Single Source Shortest Path Problem with Few Distinct Positive Lengths
by: Orlin, James B., et al.
Published: (2011) -
Directed Shortest Paths via Approximate Cost Balancing
by: Orlin, Jim
Published: (2022) -
Parameter Shortest Path Algorithms with an Application to Cyclic Staffing
by: Karp, Richard M., et al.
Published: (2004) -
DYNAMIC SHORTEST PATHS MINIMIZING TRAVEL TIMES AND COSTS
by: Ahuja, Ravindra, et al.
Published: (2003)