http://www.dagstuhl.de/06481

26. November – 01. Dezember 2006, Dagstuhl Seminar 06481

Geometric Networks and Metric Space Embeddings

Organisatoren

Joachim Gudmundsson (NICTA – Sydney, AU)
Rolf Klein (Universität Bonn, DE)
Giri Narasimhan (Florida International University – Miami, US)
Michiel Smid (Carleton University – Ottawa, CA)
Alexander Wolff (KIT – Karlsruher Institut für Technologie, DE)

Auskunft zu diesem Dagstuhl Seminar erteilt

Dagstuhl Service Team

Dokumente

Dagstuhl Seminar Proceedings DROPS
Teilnehmerliste
Dagstuhl's Impact: Dokumente verfügbar

Summary

This seminar has, for the first time, brought together scientists from three different communities who are actively working on distance problems.

Geometric networks are at the core of any model for the flows of goods, traffic or information. They also play an important role in telecommunication, VLSI design, motion planning (robotics), pattern matching, data compression, bio-informatics (gene analysis), and sensor networks. One is interested in spanners with other useful properties like a linear number of edges, small total edge length, small node degree, few crossings, or small link diameter. Apart from these applications, geometric spanners have had great impact on the construction of approximation algorithms, e.g., for the traveling salesman problem. Such problems have been investigated by researchers in computational geometry and combinatorial optimization. For storage, visualization, and retrieval of high-dimensional data the question of reducing the dimension plays a crucial rôle. This has led to a theory of metric space embeddings that was most actively developed by scientists in discrete geometry and mathematics. Finally, mathematicians and biologists are interested in metric properties and the visualization of phylogenetic networks.

For each of the three fields, a survey talk was given at the seminar (Michiel Smid: Geometric Spanner Networks, Anupam Gupta: Metric Embeddings, Daniel Huson: Application of Phylogenetic Networks in Evolutionary Studies). In addition, twenty-two regular talks were given by the seminar participants. They encouraged a fruitful exchange of ideas and stimulated interesting discussions and co-operations.

The range of interesting topics that came up during this seminar is well documented by the list of problems that were discussed in two open-problem sessions and attacked by small groups of participants in the corresponding problem-solving sessions.

Related Dagstuhl Seminar

Classification

  • Data Structures
  • Algorithms
  • Complexity

Keywords

  • Geometric networks
  • Metric space embeddings
  • Spanners
  • Dilation

Buchausstellung

Bücher der Teilnehmer 

Buchausstellung im Erdgeschoss der Bibliothek

(nur in der Veranstaltungswoche).

Dokumentation

In der Reihe Dagstuhl Reports werden alle Dagstuhl-Seminare und Dagstuhl-Perspektiven-Workshops dokumentiert. Die Organisatoren stellen zusammen mit dem Collector des Seminars einen Bericht zusammen, der die Beiträge der Autoren zusammenfasst und um eine Zusammenfassung ergänzt.

 

Download Übersichtsflyer (PDF).

Publikationen

Es besteht weiterhin die Möglichkeit, eine umfassende Kollektion begutachteter Arbeiten in der Reihe Dagstuhl Follow-Ups zu publizieren.

Dagstuhl's Impact

Bitte informieren Sie uns, wenn eine Veröffentlichung ausgehend von
Ihrem Seminar entsteht. Derartige Veröffentlichungen werden von uns in der Rubrik Dagstuhl's Impact separat aufgelistet  und im Erdgeschoss der Bibliothek präsentiert.