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
English
Note: We use this to send email in the morning.
Date, Time and Location
Wednesday, 31 October 2007
14:00
45 Minutes
E1 4
024
Saarbrücken
Abstract
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.
Contact
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 17:12
Spyros Angelopoulos, 10/21/2007 19:13 -- Created document.
Spyros Angelopoulos, 10/21/2007 19:13 -- Created document.