Girth of a Planar Digraph with Real Edge Weights in O(n(log n)^3) Time

Christian Wulff‐Nilsen

Type: Preprint

Publication Date: 2009-01-01

Citations: 2

DOI: https://doi.org/10.48550/arxiv.0908.0697

View Publication

Locations

arXiv (Cornell University) - View
DataCite API - View

Similar Works

Action	Title	Year	Authors
+	Shortest Paths in Planar Graphs with Real Lengths in $O(n\log^2n/\log\log n)$ Time	2009	Shay Mozes Christian Wulff‐Nilsen
+ PDF Chat	Shortest Paths in Planar Graphs with Real Lengths in O(nlog2 n/loglogn) Time	2010	Shay Mozes Christian Wulff‐Nilsen
+ PDF Chat	Computing the Girth of a Planar Graph in Linear Time	2013	Hsien-Chih Chang Hsueh-I Lu
+	Subquadratic Algorithms for the Diameter and the Sum of Pairwise Distances in Planar Graphs	2017	Sergio Cabello
+	Shortest-Path-Preserving Rounding	2019	Herman Haverkort David Kübel Elmar Langetepe
+	Shortest-Path-Preserving Rounding	2019	Herman Haverkort David Kübel Elmar Langetepe
+ PDF Chat	Computing the Girth of a Planar Graph in Linear Time	2011	Hsien-Chih Chang Hsueh-I Lu
+	Faster approximation algorithms for computing shortest cycles on weighted graphs	2018	Guillaume Ducoffe
+ PDF Chat	Subquadratic Algorithms for the Diameter and the Sum of Pairwise Distances in Planar Graphs	2018	Sergio Cabello
+	Minimum Cut in $O(m\log^2 n)$ Time	2019	Paweł Gawrychowski Shay Mozes Oren Weimann
+ PDF Chat	Faster single-source shortest paths with negative real weights via proper hop distance	2024	Y. P. Huang Peter Jin Kent Quanrud
+	Minimum Cut of Directed Planar Graphs in O(nloglogn) Time	2015	Shay Mozes Cyril Nikolaev Yahav Nussbaum Oren Weimann
+	Minimum Cut of Directed Planar Graphs in O(nloglogn) Time	2015	Shay Mozes Cyril Nikolaev Yahav Nussbaum Oren Weimann
+ PDF Chat	A General Purpose Algorithm for Counting Simple Cycles and Simple Paths of Any Length	2019	Pierre-Louis Giscard Nils M. Kriege Richard C. Wilson
+	Constant Girth Approximation for Directed Graphs in Subquadratic Time	2019	Shiri Chechik Yang P. Liu Omer Rotem Aaron Sidford
+	Constant Girth Approximation for Directed Graphs in Subquadratic Time	2019	Shiri Chechik Yang P. Liu Omer Rotem Aaron Sidford
+	Min st-Cut of a Planar Graph in O(n loglog n) Time	2010	Christian Wulff‐Nilsen
+	Acyclic Subgraphs of Planar Digraphs	2014	Noah Golowich David Rolnick
+ PDF Chat	Acyclic Subgraphs of Planar Digraphs	2015	Noah Golowich David Rolnick
+	Acyclic Subgraphs of Planar Digraphs	2014	Noah Golowich David Rolnick

Works That Cite This (1)

Action	Title	Year	Authors
+	Minimum Cut of Directed Planar Graphs in O(nloglogn) Time	2015	Shay Mozes Cyril Nikolaev Yahav Nussbaum Oren Weimann

Works Cited by This (2)

Action	Title	Year	Authors
+	Finding Even Cycles Even Faster	1997	Raphael Yuster Uri Zwick
+	Graph Theory and Probability	2009	P. Erdős