On the negative cost girth problem in planar networks
type: Item
instance of: scholarly article
title: On the negative cost girth problem in planar networks
zbMATH Open document ID: 1343.05144
author: Matthew Williamson
author: K. Subramani
published in: Journal of Discrete Algorithms
publication date: 2015-11-17T00:00:00Z
Mathematics Subject Classification ID: 05C82
Mathematics Subject Classification ID: 05C10
Mathematics Subject Classification ID: 05C85
zbMATH DE Number: 6510088
zbMATH Keywords: negative cost cycle detection
zbMATH Keywords: planar networks
zbMATH Keywords: girth
zbMATH Keywords: relaxation
zbMATH Keywords: divide and conquer
MaRDI profile type: Publication
full work available at URL: j.jda.2015.10.001
OpenAlex ID: W2193718508
cites work: Color-coding
cites work: Finding and counting given length cycles
cites work: Q5501344
cites work: Computing the girth of a planar graph in linear time
cites work: Q3651735
cites work: On the Problem of Partitioning Planar Graphs
cites work: Q2754199
cites work: Q4886099
cites work: Planar graphs, negative weight edges, shortest paths, and near linear time
cites work: Fast Algorithms for Shortest Paths in Planar Graphs, with Applications
cites work: Planar separators and parallel polygon triangulation.
cites work: Faster shortest-path algorithms for planar graphs
cites work: Finding a Minimum Circuit in a Graph
cites work: Improved algorithms for min cut and max flow in undirected planar graphs
cites work: Shortest paths in directed planar graphs with negative lengths
cites work: Min-Cuts and Shortest Cycles in Planar Graphs in O(n loglogn) Time
cites work: A Separator Theorem for Planar Graphs
cites work: Generalized Nested Dissection
cites work: The complexity of determining a shortest cycle of even length
cites work: Q3525910
cites work: An analysis of totally clairvoyant scheduling
cites work: Optimal length resolution refutations of difference constraint systems
cites work: Improved algorithms for optimal length resolution refutation in difference constraint systems
cites work: A Theorem on Planar Graphs
cites work: Computing the Girth of a Planar Graph in $O(n \logn)$ Time
cites work: Finding Even Cycles Even Faster
DOI: 10.1016/J.JDA.2015.10.001
description: scientific article; zbMATH DE number 6510088