[NRG] Minimum Wiener Connector Problem

Michel Machado michel at digirati.com.br
Tue Dec 2 13:59:07 EST 2014


Hi everyone,

    Natali is presenting the following talk next week that may be of 
interest of some of you.

Speaker: Natali Ruchansky
Time and place: Friday 12/12/2014 10:30am at MCS 148.

Title: Minimum Wiener Connector Problem

Abstract:
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 index.
The problem falls naturally into the class of connectivity subgraphs, 
community search, and network design problems, and has potential 
applications
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.

-- 
[ ]'s
Michel Machado


More information about the NRG-L mailing list