Search Mailing List Archives
[theory-seminar] [theory-lunch] Greg Bodwin on The Structure of Unique Shortest Paths in Graphs
Hongyang Zhang
hongyang at cs.stanford.edu
Tue Mar 13 00:06:45 PDT 2018
Hi everyone
This Thursday, Greg Bodwin (welcome back!) will tell us about *The
Structure of Unique Shortest Paths in Graphs.* See abstract below.
As before, we meet from noon to 1pm, at Gates 463a.
------------------------------------------------
Abstract:
In many graph algorithms, such as APSP, the goal is to compute shortest
path or distance information over a graph with real edge weights. It is
well known, by random reweighting, that one can assume without loss of
generality that all shortest paths in the input graph are unique. This
raises the following question: what structure can we assume about unique
shortest paths in real-weighted graphs? That is: when computing APSP, do
we really need to implicitly search over all possible sets of paths, or are
there certain structural axioms that narrow down the solution space before
we even start looking at the graph?
There is one useful and well-known structural axiom, which is that unique
shortest paths must be "consistent:" no two paths can intersect, split
apart, and then intersect again. In this talk, we will complete the list
of forbidden structures along these lines, and then we will discuss some
consequences and insights that arise from this characterization theorem.
------------------------------------------------
Best,
Hongyang
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.stanford.edu/pipermail/theory-seminar/attachments/20180313/bf8ca634/attachment-0001.html>
More information about the theory-seminar
mailing list