On the negative cost girth problem in planar networks
From MaRDI portal
Publication:891820
DOI10.1016/j.jda.2015.10.001zbMath1343.05144OpenAlexW2193718508MaRDI QIDQ891820
Matthew Williamson, K. Subramani and Vahan Mkrtchyan
Publication date: 17 November 2015
Published in: Journal of Discrete Algorithms (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.jda.2015.10.001
Small world graphs, complex networks (graph-theoretic aspects) (05C82) Planar graphs; geometric and topological aspects of graph theory (05C10) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items (2)
Empirical analysis of algorithms for the shortest negative cost cycle problem ⋮ Randomized algorithms for finding the shortest negative cost cycle in networks
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Finding and counting given length cycles
- Optimal length resolution refutations of difference constraint systems
- Planar separators and parallel polygon triangulation.
- The complexity of determining a shortest cycle of even length
- Improved algorithms for optimal length resolution refutation in difference constraint systems
- An analysis of totally clairvoyant scheduling
- Planar graphs, negative weight edges, shortest paths, and near linear time
- Min-Cuts and Shortest Cycles in Planar Graphs in O(n loglogn) Time
- Fast Algorithms for Shortest Paths in Planar Graphs, with Applications
- A Separator Theorem for Planar Graphs
- Generalized Nested Dissection
- On the Problem of Partitioning Planar Graphs
- Finding a Minimum Circuit in a Graph
- Finding Even Cycles Even Faster
- Color-coding
- Computing the Girth of a Planar Graph in $O(n \logn)$ Time
- Improved algorithms for min cut and max flow in undirected planar graphs
- A Theorem on Planar Graphs
- Computing the Girth of a Planar Graph in Linear Time
- Faster shortest-path algorithms for planar graphs
This page was built for publication: On the negative cost girth problem in planar networks
