Campus Event Calendar
Event Entry
What and Who
Low outdegree orientations of graphs and their applications
Łukasz Kowalik
Max-Planck-Institut für Informatik - AG 1
AG1 Mittagsseminar (own work)
AG 1, AG 2, AG 3, AG 4, AG 5
AG Audience
English
Note: We use this to send email in the morning.
Date, Time and Location
Monday, 14 November 2005
13:30
30 Minutes
46.1 - MPII
024
Saarbrücken
Abstract
Orientation of an undirected graph G is obtained from G by replacing each edge uv by an arc (u,v) or (v,u). There are classes of graphs like trees, planar graphs, or more generally uniformly sparse graphs, which admit "bounded outdegree orientation", for example one can find an orientation of a planar graph such that at most 3 edges leave each vertex.
I'm going to show how bounded outdegree orientations can be applied for efficient processing adjacency queries, and more generally, shortest path queries in both static and dynamic setting.
I will also discuss a related problem of finding an orientation with the lowest possible maximum outdegree. This problem can be solved in O(m*min(m^1/2,n^2/3)) time using matroid partitioning/flow techniques. However, I will focus on a very simple approximation scheme running in O(m*polylog) time.
Some open problems in this area will be mentioned.
Contact
Lukasz Kowalik
118
--email hidden
passcode not visible
logged in users only
Tags, Category, Keywords and additional notes
algorithm; graph; orientation
Lukasz Kowalik, 11/04/2005 15:59
Lukasz Kowalik, 11/04/2005 15:58 -- Created document.
Lukasz Kowalik, 11/04/2005 15:58 -- Created document.