On 19.06.2008 at 12:20, in S1, there is the following noon lecture:
Computing minimum distortion embeddings into a path
Department of Information and Computer Science, University of Oregon, USA
The problem of computing minimum distortion embeddings of a given graph into a line (path) was introduced in 2004 and has quickly attracted significant attention with subsequent results appearing in recent STOC and SODA conferences. So far all such results concern approximation algorithms or exponential-time exact algorithms. We give the first polynomial-time algorithms for computing minimum distortion embeddings of graphs into a path when the input graphs belong to specific graph classes. In particular, we solve this problem in polynomial time for bipartite permutation graphs and threshold graphs.
Joint work with Pinar Heggernes and Daniel Meister, Bergen, Norway.
Webmaster: kamweb.mff.cuni.cz Modified: 19. 10. 2010