REVIEW 1 cited by
Subquadratic Algorithms for the Diameter and the Sum of Pairwise Distances in Planar Graphs
Not yet reviewed by Pith; the record is open.
This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.
SPECIMEN: schema-true, not a live event
T0 review · schema-true
One-sentence machine reading of the paper's core claim.
pith:XXXXXXXX · record.json · timestamp
Signed reviews
abstract
We show how to compute for $n$-vertex planar graphs in $O(n^{11/6}{\rm polylog}(n))$ expected time the diameter and the sum of the pairwise distances. The algorithms work for directed graphs with real weights and no negative cycles. In $O(n^{15/8}{\rm polylog}(n))$ expected time we can also compute the number of pairs of vertices at distance smaller than a given threshold. These are the first algorithms for these problems using time $O(n^c)$ for some constant $c<2$, even when restricted to undirected, unweighted planar graphs.
Forward citations
Cited by 1 Pith paper
-
Finding Regions of Maximum Circularity in Plane Geometric Graphs
Maximizing A/P^α over unions of faces in a plane subdivision is weakly NP-hard for α in (1,2] and solvable in pseudopolynomial time for all α>1.
Discussion (0). Continue with ORCID to comment.