On the negative cost girth problem in planar networks

DOI10.1016/J.JDA.2015.10.001zbMATH Open1343.05144OpenAlexW2193718508MaRDI QIDQ891820FDOQ891820

K. Subramani, Matthew Williamson

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)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Generalized Nested Dissection
• Color-coding
• Finding and counting given length cycles
• The complexity of determining a shortest cycle of even length
• A Separator Theorem for Planar Graphs
• Fast Algorithms for Shortest Paths in Planar Graphs, with Applications
• On the Problem of Partitioning Planar Graphs
• Finding a Minimum Circuit in a Graph
• Faster shortest-path algorithms for planar graphs
• A Theorem on Planar Graphs
• Planar graphs, negative weight edges, shortest paths, and near linear time
• Shortest paths in directed planar graphs with negative lengths
• Min-Cuts and Shortest Cycles in Planar Graphs in O(n loglogn) Time
• Improved algorithms for min cut and max flow in undirected planar graphs
• An analysis of totally clairvoyant scheduling
• Planar separators and parallel polygon triangulation.
• Finding Even Cycles Even Faster
• Improved algorithms for optimal length resolution refutation in difference constraint systems
• Optimal length resolution refutations of difference constraint systems
• Computing the girth of a planar graph in linear time
• Computing the Girth of a Planar Graph in $O(n \logn)$ Time

Cited In (2)

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

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)