[Dmbu-l] no seminar this week. Next week: Natali Ruchansky on her work at Yahoo
edori at bu.edu
Tue Dec 2 11:30:02 EST 2014
there will be no seminar talk this week, but next week Natali is going to
give us a talk on her work at Yahoo. I will send a reminder next week, but
FYI I am copying the abstract here as well.
Enjoy your week!
Title: Minimum Wiener Connector Problem
The Wiener index of a graph is the sum of all pairwise shortest-path
distances between its vertices.
In a recently submitted paper we study the novel problem of finding a
minimum Wiener connector: given a connected graph G=(V,E) and a set Q
subset of V of query vertices, find a
subgraph of G that connects all query vertices and has minimum Wiener
The problem falls naturally into the class of connectivity subgraphs,
community search, and network design problems, and has potential
in many scenarios, including visualization in online tools, finding
community leaders, and finding bridges between communities.
In this talk I will give a historic introduction to the notion of Wiener
index, how it differs from the more-known concept of Steiner tree, and
give some simple heuristic algorithms for the Wiener Connector Problem.
I'll also give a sample of experiments on real-world graphs, and cute toy
examples on the Karate-Club network, and a 2014 KDD tweet graph.
Time permitting I will also give an (very) high-level taste of some
theoretical results in the paper -- in particular of our main contribution
is a constant-factor approximation algorithm running in
time O(|Q||E|), and of a comparison to a linear programming formulation.
More information about the Dmbu-l