Dagstuhl Seminar 06481
Geometric Networks and Metric Space Embeddings
( Nov 26 – Dec 01, 2006 )
(Click in the middle of the image to enlarge)
Permalink
Please use the following short url to reference this page:
https://www.dagstuhl.de/06481
Organizers
- 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)
Contact
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.
- Helmut Alt (FU Berlin, DE) [dblp]
- Mattias Andersson (Lund University, SE)
- Hans-Jürgen Bandelt (Universitätsklinikum Hamburg-Eppendorf, DE)
- Marc Benkert (KIT - Karlsruher Institut für Technologie, DE)
- Sergey Bereg (University of Texas at Dallas, US)
- Prosenjit Bose (Carleton University - Ottawa, CA)
- Hans Burkhardt (Universität Freiburg, DE)
- Sergio Cabello (University of Ljubljana, SI) [dblp]
- Hubert Chan (MPI für Informatik - Saarbrücken, DE) [dblp]
- Otfried Cheong (KAIST - Daejeon, KR) [dblp]
- Victor Chepoi (Aix-Marseille University, FR)
- Sebastien Collette (University of Brussels, BE)
- Mark de Berg (TU Eindhoven, NL) [dblp]
- Adrian Dumitrescu (Univ. Wisconsin - Milwaukee, US)
- Mohammad Farshi (TU Eindhoven, NL)
- Sándor Fekete (TU Braunschweig, DE) [dblp]
- Rudolf Fleischer (Fudan University - Shanghai, CN) [dblp]
- Ansgar Grüne (Universität Bonn, DE)
- Joachim Gudmundsson (NICTA - Sydney, AU) [dblp]
- Anupam Gupta (Carnegie Mellon University, US) [dblp]
- Herman J. Haverkort (TU Eindhoven, NL) [dblp]
- Ferran Hurtado (UPC - Barcelona, ES)
- Daniel H. Huson (Universität Tübingen, DE) [dblp]
- Piotr Indyk (MIT - Cambridge, US) [dblp]
- Matthew J. Katz (Ben Gurion University - Beer Sheva, IL) [dblp]
- Michael Kaufmann (Universität Tübingen, DE) [dblp]
- Rolf Klein (Universität Bonn, DE) [dblp]
- Christian Knauer (FU Berlin, DE) [dblp]
- Stefan Langerman (Free University of Brussels, BE) [dblp]
- Anil Maheshwari (Carleton University - Ottawa, CA)
- Pat Morin (Carleton University - Ottawa, CA) [dblp]
- Vincent Moulton (University of East Anglia - Norwich, GB) [dblp]
- Giri Narasimhan (Florida International University - Miami, US) [dblp]
- Ilan Newman (University of Haifa, IL) [dblp]
- Kirk Pruhs (Univ. of Pittsburgh, US) [dblp]
- Yuri Rabinovich (University of Haifa, IL)
- Günter Rote (FU Berlin, DE) [dblp]
- Anastasios Sidiropoulos (University of Toronto, CA) [dblp]
- Meera Sitharam (University of Florida - Gainesville, US)
- Michiel Smid (Carleton University - Ottawa, CA)
- Christian Sohler (Universität Paderborn, DE) [dblp]
- Jan Vahrenhold (Universität Münster, DE) [dblp]
- Marc van Kreveld (Utrecht University, NL) [dblp]
- Alexander Wolff (KIT - Karlsruher Institut für Technologie, DE) [dblp]
- Martin Zachariasen (University of Copenhagen, DK)
Related Seminars
- Dagstuhl Seminar 09451: Geometric Networks, Metric Space Embeddings and Spatial Data Mining (2009-11-01 - 2009-11-06) (Details)
Classification
- data structures
- algorithms
- complexity
Keywords
- geometric networks
- metric space embeddings
- spanners
- dilation
