On the negative cost girth problem in planar networks

DOI10.1016/J.JDA.2015.10.001MaRDI QIDQ891820zbMATH OpenOpenAlexFDO

Authors Matthew Williamson, K. Subramani

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

zbMATH Keywords

girthrelaxationdivide and conquernegative cost cycle detectionplanar networks

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Small world graphs, complex networks (graph-theoretic aspects) (05C82) Planar graphs; geometric and topological aspects of graph theory (05C10)

Recommendations

• scientific article; zbMATH DE number 1670873
• Computing the Girth of a Planar Graph in O(n logn) Time
• Computing the girth of a planar graph in \(O(n \log n)\) time

Cites work

• scientific article; zbMATH DE number 1670873 (Why is no real title available?)
• Title not available (Why is no real title available?)
• scientific article; zbMATH DE number 5345853 (Why is no real title available?)
• scientific article; zbMATH DE number 910922 (Why is no real title available?)
• scientific article; zbMATH DE number 6469225 (Why is no real title available?)
• A Separator Theorem for Planar Graphs
• A Theorem on Planar Graphs
• An analysis of totally clairvoyant scheduling
• Color-coding
• Computing the girth of a planar graph in \(O(n \log n)\) time
• Fast Algorithms for Shortest Paths in Planar Graphs, with Applications
• Faster shortest-path algorithms for planar graphs
• Finding Even Cycles Even Faster
• Finding a Minimum Circuit in a Graph
• Finding and counting given length cycles
• Generalized Nested Dissection
• Improved algorithms for min cut and max flow in undirected planar graphs
• Improved algorithms for optimal length resolution refutation in difference constraint systems
• Introduction to algorithms.
• Min-cuts and shortest cycles in planar graphs in \(O(n \log\log n)\) time
• On the Problem of Partitioning Planar Graphs
• Optimal length resolution refutations of difference constraint systems
• Planar graphs, negative weight edges, shortest paths, and near linear time
• Planar separators and parallel polygon triangulation.
• The complexity of determining a shortest cycle of even length

Cited in

(2)

• Randomized algorithms for finding the shortest negative cost cycle in networks
• Empirical analysis of algorithms for the shortest negative cost cycle problem

This page was built for publication: On the negative cost girth problem in planar networks

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q891820)