Please note: These two PhD seminars will be given online.
Bryce
Sandlund, PhD
candidate
David
R.
Cheriton
School
of
Computer
Science
A
Simple
Algorithm
for
Minimum
Cuts
in
Near-Linear
Time
We
consider
the
minimum
cut
problem
in
undirected,
weighted
graphs.
We
give
a
simple
algorithm
to
find
a
minimum
cut
that
2-respects
(cuts
two
edges
of)
a
spanning
tree
T
of
a
graph
G.
This
procedure
can
be
used
in
place
of
the
complicated
subroutine
given
in
Karger’s
near-linear
time
minimum
cut
algorithm
(J.
ACM,
2000).
We
give
a
self-contained
version
of
Karger’s
algorithm
with
the
new
procedure,
which
is
easy
to
state
and
relatively
simple
to
implement.
It
produces
a
minimum
cut
on
an
m-edge,
n-vertex
graph
in
O(m
log^3
n)
time
with
high
probability,
matching
the
complexity
of
Karger’s
approach.
Space-Efficient
Data
Structures
for
Lattices
A
lattice
is
a
partially-ordered
set
in
which
every
pair
of
elements
has
a
unique
meet
(greatest
lower
bound)
and
join
(least
upper
bound).
We
present
new
data
structures
for
lattices
that
are
simple,
efficient,
and
nearly
optimal
in
terms
of
space
complexity.
Our first data structure can answer partial order queries in constant time and find the meet or join of two elements in O(n^(3/4)) time, where n is the number of elements in the lattice. It occupies O(n^(3/2) logn) bits of space, which is only a Θ(logn) factor from the Θ(n^(3/2))-bit lower bound for storing lattices. The preprocessing time is O(n^2). This structure admits a simple space-time tradeoff so that, for any c ∈ [1/2,1], the data structure supports meet and join queries in O(n^(1−c/2)) time, occupiesO(n^(1+c) log n) bits of space, and can be constructed in O(n^2+n^(1+3c/2)) time.
Our second data structure uses O(n^(3/2) log n) bits of space and supports meet and join in O(d log n /log d) time, where d is the maximum degree of any element in the transitive reduction graph of the lattice. This structure is much faster for lattices with low-degree elements.
This paper also identifies an error in a long-standing solution to the problem of representing lattices. We discuss the issue with this previous work.