Campus Event Calendar

Event Entry

What and Who

The Online Steiner Tree Problem in Directed Graphs

Spyros Angelopoulos
Max-Planck-Institut für Informatik - D1
AG1 Mittagsseminar (own work)
AG 1  
AG Audience

Date, Time and Location

Wednesday, 31 October 2007
45 Minutes
E1 4


The Steiner Tree problem in graphs is one of the fundamental problems in combinatorial optimization: given an edge-weighted graph and a specified subset of its vertices, we seek the minimum-cost subgraph that spans the subset in question. Most of the existing work on Steiner trees is focused on undirected graphs; however, in several applications (e.g., algorithms over the internet) the underlying graph is in fact directed.

In this talk I will present some recent work on the online version of the problem. Namely, requests appear in a sequence, and we want to maintain a Steiner arborescence of small cost. The analysis appeals to the concept of the edge-asymmetry of a graph, defined as the maximum ratio of the weights of antiparallel edges in the graph.
I will also outline some related variations of the Steiner tree problem which, likewise, apply in the on-line setting.


Spyros Angelopoulos
--email hidden
passcode not visible
logged in users only

Tags, Category, Keywords and additional notes

Online algorithms; Steiner tree problems

Spyros Angelopoulos, 10/22/2007 05:12 PM
Spyros Angelopoulos, 10/21/2007 07:13 PM -- Created document.