Universiteit van Amsterdam

Archives

Institute for Logic, Language and Computation

Please note that this newsitem has been archived, and may contain outdated information or links.

11 December 2014, Theoretical Computer Science Seminar, David Garcia Soriano

Speaker: David Garcia Soriano (Yahoo Labs, Barcelona)
Title: The Minimum Wiener Connector Problem
Date: Thursday 11 December 2014
Time: 16:00-17:00
Location: CWI room L017, Science Park 123, Amsterdam

Abstract

The Wiener index of a graph is the sum of all pairwise shortest-path distances between its vertices. In this paper we study the novel problem of finding a minimum Wiener connector: given a connected graph G=(V,E) and a set Q\subseteq 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. The Minimum Wiener Connector Problem admits a polynomial-time exact algorithm for the special case where the number of query vertices is bounded. We show that in the general case the problem is NP-hard and has no PTAS unless P=NP. Our main contribution is a constant-factor approximation algorithm running in time ~O(|Q||E|). A thorough experimentation on a large variety of real-world graphs confirms the practical efficiency and accuracy of our algorithm; our returned subgraphs are smaller and denser than those produced by other methods.

Joint work with Natali Ruchansky (Boston University), Francesco Bonchi (Yahoo Labs), Francesco Gullo (Yahoo Labs) and Nicolas Kourtellis (Yahoo Labs).

For more information, contact

Please note that this newsitem has been archived, and may contain outdated information or links.