Campus Event Calendar
Event Entry
New for: D3
What and Who
Approximating bandwidth by mixing layouts of interval graphs
Dieter Kratsch
Universität Metz
Lecture
AG 1, AG 2, AG 3, AG 4
AG Audience
English
Note: We use this to send email in the morning.
Date, Time and Location
Wednesday, 28 June 2000
13:30
45 Minutes
MPI
o24
Saarbrücken
Abstract
Abstract: We consider the bandwidth minimization problem
for graphs as a classical NP-hard optimization
problem on graphs that even remains NP-hard on trees.
We present an efficient algorithm to approximate
the bandwidth of circular-arc graphs within a
factor of 2, which is the best possible factor
achievable (unless P=NP).
Contact
Kurt Mehlhorn
--email hidden
passcode not visible
logged in users only