Peter Widmayer

Arbitrary Pattern Formation by Asynchronous, Anonymous, Oblivious Robots ∗ (2009)

A group of mobile autonomous robots, each with very limited capabilities, can form (complex) patterns in the space it occupies. These patterns can be used to program the robots to accomplish...

From an engineering point of view, the problem of coordinating a set of autonomous, mobile robots for the purpose of cooperatively performing a task has been studied extensively over the past decade....

A Distributed Algorithm for All Best Swap Edges of a Minimum Diameter Spanning Tree ∗ (Regular Submission) (2008)

Abstract. Given a 2-node connected, real weighted, and undirected graph G = (V, E), with n nodes and m edges, and given a minimum spanning tree (MST) T = (V, ET) of G, we study the problem of...

Beat Gfeller, Nicola Santoro, Peter Widmayer

Communication in networks suffers if a link fails. When the links are edges of a tree that has been chosen from an underlying graph of all possible links, a broken link even disconnects the network....

Abstract Pre-Analysis Locking: A Safe and Deadlock Free Locking Policy (2008)

Georg Lausen, Eljas Soisalon-soininen, Peter Widmayer

A safe and deadlock free lock policy is introduced, called pre-analysis locking. Pre-analysis locking is based on an efficient geometric algorithm which inserts lock and unlock operations into the...

Optimization Problems in Mobile Communication (2008)

Prof Dr, Peter Widmayer, Eth Zürich

In one way or another mobile phones have changed everyone’s life. Mobile communication networks made it possible to be connected and reachable even in the most remote places. A lot of research...

DISCRETE APPLIED (2008)

Edmund Ihler A, Gabriele Reich B, Peter Widmayer

We consider a generalized version of the Steiner problem in graphs, motivated by the wire routing phase in physical VLSI design: given a connected, undirected distance graph with required classes of...

On the robustness of Graham’s algorithm for online scheduling (2008)

Michael Gatto, Peter Widmayer

Abstract. While standard parallel machine scheduling is concerned with good assignments of jobs to machines, we aim to understand how the quality of an assignment is affected if the jobs ’...

index (2008)

Jörg Derungs, Riko Jacob, Peter Widmayer

shortest paths guided by a small

Theory on the Tracks: A Selection of Railway Optimization Problems (2008)

Michael Gatto, Riko Jacob, Leon Peeters, Birgitta Weber, Peter Widmayer

Railway optimization problems have been studied from a mathematical programming perspective for decades. This approach is particularly well suited to model the multitude of constraints that typically...

accepted on the recommendation of (2008)

Prof Dr, Peter Widmayer, Eth Zürich, Prof Dr, Klaus Jansen, ...

Scheduling problems arise in various application areas in industry, planning, and timetabling. These problems have been subject of extensive research not only in the area of computer science but also...

Abstract Towards an Analysis of Range Query Performance in Spatial Data Structures* (2008)

Hans-werner Six, Heinrich Toben, Peter Widmayer

In this paper, we motivate four different user defined window query classes and derive a probabilistic model for each of them. For each model, we characterize the efficiency of spatial data...

Interpreting Abstract (2008)

Bernd Fischer, Volker Roth, Joachim M. Buhmann, Jonas Grossmann, Sacha Baginsky, Wilhelm Gruissem, ...

De novo Sequencing of peptides is a challenging task in proteome research. While there exist reliable DNA-sequencing methods, the highthroughput de novo sequencing of proteins by mass spectrometry is...

Towards Decentralized Distributed Data Structures (2008)

ATMOS 2008 Preface -- 8th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (2008)

We motivate and present a simple measure of efficiency for distributed data structures called "bottleneck complexity". We investigate a distributed counter as a case study for our measure...

Fischetti, Matteo, Widmayer, Peter

The 8th ATMOS workshop was held in Karlsruhe, September 18, 2008, within ALGO, a set of meetings related to algorithms. The series of ATMOS workshops, starting in Heraklion in 2001, continuing in...

ATMOS 2008 Abstracts Collection -- 8th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (2008)

Fischetti, Matteo, Widmayer, Peter

Proceedings of the 8th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems, held on Septmeber 18 in Karlsruhe, Germany.

Genevestigator V3: A Reference Expression Database for the Meta-Analysis of Transcriptomes (2008)

Tomas Hruz, Oliver Laule, Gabor Szabo, Frans Wessendorp, Stefan Bleuler, Lukas Oertle, ...

The Web-based software tool Genevestigator provides powerful tools for biologists to explore gene expression across a wide variety of biological contexts. Its first releases, however, were limited by...

A Prototype System for Light Propagation in Terrains (2007)

Christoph Stamm, Stephan Eidenbenz, Michael Beck, Peter Stucki, Peter Widmayer

We present a prototype system for a simple version of electro-magnetic wave propagation prediction in rural areas, using a real-time exploration environment for very large topographic scenes. The...

An Asymptotically Optimal Multiversion B-Tree (2007)

Prof Dr, Peter Widmayer, Deutsche Forschungsgemeinschaft Dfg, Bruno Becker, ...

In a variety of applications, we need to keep track of the development of a data set over time. For maintaining and querying these multiversion data efficiently, external storage structures are an...

On Optimal Cuts of Hyperrectangles (2007)

Fabrizio D'Amore, Viet Hai Nguyen, Thomas Roos, Peter Widmayer

We are given a set of n d-dimensional (possibly intersecting) isothetic hyperrectangles. The topic of this paper is the separation of these rectangles by means of a cutting isothetic hyperplane....

Fast Counting with the Optimum Combining Tree (2007)

A distributed counter is a concurrent object which provides a test-and-incrementoperation on a shared value. On the basis of a distributed counter, one can implement various fundamental data...

2 (2007)

An Approximation Algorithm for Minimum Convex Cover with Logarithmic Performance Guarantee; manuscript (2007)

Abstract. In this paper we aim at an understanding of the fundamental algorithmic limitations on what a set of autonomous mobile robots can or cannot achieve. We study a hard task for a set of weak...

Stephan Eidenbenz, Peter Widmayer

Abstract. The problem Minimum Convex Cover of covering a given polygon with a minimum number of (possibly overlapping) convex polygons is known to be NP-hard, even for polygons without holes [3]. We...

z (2007)

Aris Pagourtzis, Paolo Penna, Konrad Schlude, Kathleen Steinhofel, David Scot Taylor, Peter Widmayer

Dominating sets in their many variations model a wealth of optimization problems like facility location or distributed file sharing. For instance, when a request can occur at any node in a graph and...

accepted on the recommendation of (2007)

Roger Peter Wattenhofer, Peter Widmayer, Prof Dr, Prof Dr, Maurice Herlihy

"Can you do addition? " the White Queen asked. "What's one and one and one and one and one and one and one and one and one and one?" "I don't...

Minimum Diameter Spanning Tree Under Transient Edge Failures (2007)

Srinivas R. Doddi, Madhav V. Marathe, S. S. Ravi, David Scot Taylor, Peter Widmayer

In network communication systems, frequently messages are routed along a minimum diameter spanning tree (MDST) of the network, to minimize the maximum delay in delivering a message. When a transient...

z (2007)

Thomas Erlebach, Martin Gantenbein, Daniel Hurlimann, Gabriele Neyer, Aris Pagourtzis, Paolo Penna, ...

k We consider a problem faced by train companies: How can trains be assigned to satisfy scheduled routes in a cost efficient way? Currently, many railway companies create solutions by hand, a...

3 (2007)

c flSpringer-Verlag 1

and (2007)

Counting Targets with Mobile Sensors in an Unknown Environment (2007)

A trip through a virtual world is a powerful metaphor and a natural wayofinteracting with a geographic information system (GIS). Virtual reality (VR) systems provide visual realism and real-time...

Subhash Suri, Beat Gfeller, Elias Vicari, Peter Widmayer

We consider the problem of counting the number of indistinguishable targets using a simple binary sensing model. Our setting includes an unknown number of point targets in a (simply- or...

07151 Abstracts Collection -- Geometry in Sensor Networks (2007)

Suri, Subhash, Wattenhofer, Roger, Widmayer, Peter

From 9.4.2007 to 13.4.07, the Dagstuhl Seminar 07151 ``Geometry in Sensor Networks'' was held in the International Conference and Research Center (IBFI), Schloss Dagstuhl. During the seminar, several...

accepted on the recommendation of (2006)

Franz Roos, Franz Roos, Prof Dr, Peter Widmayer, Prof Dr, Wilhelm Gruissem, ...

Bioinformatics is a hybrid science at the interface between biology and computer science. For nearly two centuries, data acquisition in the wet lab and in the field has limited the pace of progress...

Gathering of asynchronous robots with limited visibility (2005)

Geometric routing without geometry (2005)

In this paper we study the problem of gathering in the same location of the plane a collection of identical oblivious mobile robots. Previous investigations have focused mostly on the unlimited...

Mirjam Wattenhofer, Roger Wattenhofer, Peter Widmayer

Abstract. In this paper we propose a new routing paradigm, called pseudogeometric routing. In pseudo-geometric routing, each node u of a network of computing elements is assigned a pseudo coordinate...

Railway Delay Management: Exploring its Algorithmic Complexity (2004)

Michael Gatto, Bjoern Glaus, Riko Jacob, Leon Peeters, Peter Widmayer

We consider delay management in railway systems. Given delayed trains, we want to find a waiting policy for the connecting trains minimizing the weighted total passenger delay. If there is a single...

Railway delay management: Exploring its algorithmic complexity (2004)

Michael Gatto, Björn Glaus, Riko Jacob, Leon Peeters, Peter Widmayer

Abstract. We consider delay management in railway systems. Given delayed trains, we want to find a waiting policy for the connecting trains minimizing the weighted total passenger delay. If there is...

An algorithmic view on OVSF code assignment ∗ (2003)

Thomas Erlebach, Riko Jacob, Matúš Mihaľák, Marc Nunkesser, Gábor Szabó, ...

Orthogonal Variable Spreading Factor (OVSF) codes can be used to share the radio spectrum among several connections of possibly different bandwidth, which is used for example in UMTS. The...

Evolutionary multiobjective optimization for base station transmitter placement with frequency assignment (2003)

Nicole Weicker, Gabor Szabo, Karsten Weicker, Peter Widmayer

We propose a new solution to the problem of positioning base station transmitters of a mobile phone network and assigning frequencies to the transmitters, both in an optimal way. Since an exact...

Energy Optimal Routing in Radio Networks Using Geometric Data Structures (2002)

Beier, Rene, Sanders, Peter, Sivadasan, Naveen, Widmayer, Peter, Triguero, Francisco, Morales, Rafael, ...

Randomized Pursuit-Evasion in Graphs (2002)

Adler, Micah, Räcke, Harald, Sivadasan, Naveen, Sohler, Christian, Vöcking, Berthold, Widmayer, Peter, ...

{ We analyze a randomized pursuit-evasion game on graphs. This game is played by two players, a {\em hunter} and a {\em rabbit}. Let $G$ be any connected, undirected graph with $n$ nodes. The game is...

The Structure and Complexity of Nash Equilibria for a Selfish Routing Game (2002)

Fotakis, Dimitris, Kontogiannis, Spyros, Koutsoupias, Elias, Mavronicolas, Marios, Spirakis, Paul G., Widmayer, Peter, ...

In this work, we study the combinatorial structure and the computational complexity of Nash equilibria for a certain game that models {\em selfish routing} over a network consisting of $m$ parallel...

Improving customer proximity to railway stations (2002)

Evangelos Kranakis, Paolo Penna, Konrad Schlude, David Scot Taylor, Peter Widmayer

We consider problems of (nev) station placement along (existing) railvay tracks, so as to increase the number of users. We prove that, in spite of the NP-hardness for the general version, some...

Improving customer proximity to railway stations (2002)

Evangelos Kranakis, Paolo Penna, Konrad Schlude, David Scot Taylor, Peter Widmayer

Abstract. We consider problems of (new) station placement along (existing) railway tracks, so as to increase the number of users. We prove that, in spite of the NP-hardness for the general version,...

Improving customer proximity to railway stations (2002)

Evangelos Kranakis, Paolo Penna, Konrad Schlude, David Scot Taylor, Peter Widmayer

Abstract. We consider problems of (new) station placement along (existing) railway tracks, so as to increase the number of users. We prove that, in spite of the NP-hardness for the general version,...

Improving customer proximity to railway stations (2002)

Evangelos Kranakis, Paolo Penna, Konrad Schlude, David Scot Taylor, Peter Widmayer

We consider problems of (nev) station placement along (existing) railvay tracks, so as to increase the number of users. We prove that, in spite of the NP-hardness for the general version, some...

Finding the most vital node of a shortest path (2001)

Pattern Formation by Autonomous Robots Without Chirality (2001)

Abstract. In an undirected, 2-node connected graph G =(V,E) with positive real edge lengths, the distance between anytwo nodes r and s is the length of a shortest path between r and s in G. The...

Paola Flocchini, Giuseppe Prencipe, Nicola Santoro, Peter Widmayer

Consider a set of anonymous mobile robots, and the patterns they can collectively form in the plane. If each robot has a compass needle that indicates North but there is no agreement on East and West...

Distributed Highly Available Search Trees (2001)

Konrad Schlude, Eljas Soisalon-soininen, Peter Widmayer

We propose a distributed dictionary that tolerates arbitrary single server crashes. The distinctive feature of our model is that the crash of a server cannot be detected. This is in contrast to all...

Distributed Highly Available Search Trees (2001)

Konrad Schlude, Eljas Soisalon-soininen, Peter Widmayer

We propose a distributed dictionary that tolerates arbitrary single server crashes. The distinctive feature of our model is that the crash of a server cannot be detected. This is in contrast to all...

Distributed Highly Available Search Trees (2001)

Konrad Schlude, Peter Widmayer

We propose a distributed dictionary that tolerates arbitrary single server crashes. The distinctive feature of our model is that the crash of a server cannot be detected. This is in contrast to all...

Gathering of Asynchronous Oblivious Robots with Limited Visibility (2001)

Paola Flocchini, Giuseppe Prencipe, Nicola Santoro, Peter Widmayer

We consider a collection of robots which are identical (anonymous) , have limited visibility of the environment, and no memory of the past (oblivious); furthermore, they are totally asynchronous in...

Virtual Reality and Dynamic Statistical Graphics: A Bidirectional Link in a Heterogeneous, Distributed Computing Environment (2000)

Martin Schneider, Christoph Stamm, Jurgen Symanzik, Peter Widmayer

Abstract We present the implementation of a bidirectional link between RA 3 DIO and XGobi, based on the middleware standard DCE. RA 3 DIO is a virtual reality framework for the design and management...

An Image Compression Method for Spatial Search (2000)

Renato Pajarola, Prof Dr, Prof Dr, Peter Widmayer

The maintenance of large raster images under spatial operations is still a major performance bottleneck. For reasons of storage space, images in a collection, such as satellite pictures in geographic...

Über die Deposition dicker spannungsarmer kubischer Bornitridschichten [Elektronische Ressource] : eine Anwendung des Verspannungsabbaus durch mittelenergetische Ionenbestrahlung / (1999)

Widmayer, Peter.

Titel auf der Beil.

Swapping a failing edge of a single source shortest paths tree is good and fast (1999)

Swapping a failing edge of a single source shortest paths tree is good and fast (1999)

Abstract. Let G = (V, E) be a 2-edge connected, undirected and nonnegatively weighted graph, and let S(r) be a single source shortest paths tree (SPT) of G rooted at r ∈ V. Whenever an edge e in...

The Bulk Index Join: A Generic Approach to Processing Non-Equijoins (1999)

Abstract. In this paper we introduce the notion of best swap for a failing edge of a single source shortest paths tree (SPT) S(r) rooted in r in a weighted graph G =(V,E). Given an edge e ∈ S(r),...

Bernhard Seeger, Peter Widmayer

: Efficient join algorithms have been developed for processing different types of non-equijoins like spatial join, band join, temporal join or similarity join. Each of these previously proposed join...

The Bulk Index Join: (1999)

Generic Approach To, Bernhard Seeger, Peter Widmayer

Efficient join algorithms have been developed for processing different types of non-equijoins like spatial join, band join, temporal join or similarity join. Each of these previously proposed join...

The Bulk Index Join: A Generic Approach to Processing Non-Equijoins (1999)

Bernhard Seeger, Peter Widmayer

Efficient join algorithms have been developed for processing different types of non-equijoins like spatial join, band join, temporal join or similarity join. Each of these previously proposed join...

Positioning Guards at Fixed Height above a Terrain - an Optimum Inapproximability Result (1998)

Stephan Eidenbenz, Christoph Stamm, Peter Widmayer

. We study the problem of minimizing the number of guards positioned at a fixed height h such that each triangle on a given 2.5dimensional triangulated terrain T is completely visible from at least...

Inapproximability of Some Art Gallery Problems (1998)

Stephan Eidenbenz, Christoph Stamm, Peter Widmayer

We prove that the three art gallery problems Vertex Guard, Edge Guard and Point Guard for simple polygons with holes cannot be approximated by any polynomial time algorithm with a ratio of 1\Gammaffl...

XGobi And XploRe Meet Virgis (1998)

Jürgen Symanzik, Renato Pajarola, Peter Widmayer

In this paper we report on a linked environment of the three programs XGobi, XploRe, and ViRGIS. While XGobi and XploRe are statistical packages that focus on dynamic statistical graphics and provide...

The Alps at your Fingertips: Virtual Reality and Geoinformation Systems (1998)

Renato Pajarola, Thomas Ohler, Peter Stucki, Kornel Szabo, Peter Widmayer

We advocate a desktop virtual reality (VR) interface to a geographic information system (GIS). The navigational capability to explore large topographic scenes is a powerful metaphor and a natural way...

Virtual Geoexploration: Concepts And Design Choices (1998)

Finding All the Best Swaps of a Minimum Diameter Spanning Tree Under Transient Edge Failures (1998)

A trip through a virtual world is a powerful metaphor and a natural way of interacting with a geographic information system (GIS). Virtual reality (VR) systems provide visual realism and real-time...

A Prototype System for Light Propagation in Terrains (1998)

In network communication systems, frequently messages are routed along a minimum diameter spanning tree (MDST) of the network, to minimize the maximum delay in delivering a message. When a transient...

Christoph Stamm Stephan, Stephan Eidenbenz, Michael Beck, Peter Stucki, Peter Widmayer

We present a prototype system for a simple version of electro-magnetic wave propagation prediction in rural areas, using a real-time exploration environment for very large topographic scenes. The...

Singularities Make Spatial Join Scheduling Hard (1997)

Gabriele Neyer, Peter Widmayer

. The efficiency of database join operations depends crucially on how page fetches are scheduled. In general, finding an optimum schedule is NP-hard. We show that for a class of popular spatial...

The Counting Pyramid (1997)

Singularities Make Spatial Join Scheduling Hard (1997)

A distributed counter is a concurrent object which provides a test-and-incrementoperation on a shared value. On the basis of a distributed counter, one can implement various fundamental data...

Gabriele Neyer, Peter Widmayer

It is long known that scheduling relational joins, where relations reside on disk, is NP-hard in general. This result motivated a number of heuristics for scheduling spatial joins, where spatial data...

Low-Cost Fault-Tolerant Spanning Graphs for Point Sets in the Euclidean Plane (1997)

Enrico Nardelli, Ulrike Stege, Peter Widmayer

The concept of the minimum spanning tree (MST) plays an important role in topological network design, because it models a cheapest connected network. In a tree, however, the failure of a vertex can...

An Inherent Bottleneck in Distributed Counting (1997)

Distributed Counting at Maximum Speed (1997)

A distributed counter allows each processor in an asynchronous message passing network to access the counter value and increment it. We study the problem of implementing a distributed counter such...

An Inherent Bottleneck in Distributed Counting (1997)

this paper, we propose an efficient linearizable counter. The definition of efficiency for distributed data structures in general and for a distributed counter in particular is not as immediate as in...

Singularities Make Spatial Join Scheduling Hard (1997)

A distributed counter allows each processor in an asynchronous message passing network to access the counter value and increment it. We study the problem of implementing a distributed counter such...

Gabriele Neyer, Peter Widmayer

. The efficiency of database join operations depends crucially on how page fetches are scheduled. In general, finding an optimum schedule is NP-hard. We show that for a class of popular spatial...

Relaxed Balance through Standard Rotations (1997)

Kim S. Larsen, Eljas Soisalon-soininen, Peter Widmayer

We consider binary search trees, where rebalancing transformations need not be connected with updates but may be delayed. For standard AVL tree rebalancing, we prove that even though the rebalancing...

A generic approach to bulk loading multidimensional index structures (1997)

Jochen Bercken, Bernhard Seeger, Peter Widmayer, Fachgebiet Informatik

Abstract: Recently there has been an increasing interest in supporting bulk operations on multidimensional index structures. Bulk loading refers to the process of creating an initial index structure...

Pattern Matching in Compressed Raster Images (1996)

Spatial Indexing into Compressed Raster Images: How to Answer Range Queries Without Decompression (1996)

We study the problem of finding a two-dimensional pattern in a compressed satellite image. We present an algorithm that solves this problem without decompressing the image. The runtime of our...

An asymptotically optimal multiversion B-tree (1996)

The maintenance of large raster images under spatial operations is still a major performance bottleneck. For reasons of storage space, images in a collection, such as satellite pictures in geographic...

Bruno Becker, Stephan Gschwind, Thomas Ohler, Bernhard Seeger, Peter Widmayer

.<F3.733e+05> In a variety of applications, we need to keep track of the development of a data set over time. For maintaining and querying these multiversion data efficiently, external storage...

Pattern matching in compressed raster images (1996)

An Asymptotically Optimal Multiversion B-tree (1996)

We study the problem of nding a two-dimensional pattern in a compressed satellite image. We present an algorithm that solves this problem without decompressing the image. The runtime of our algorithm...

Bruno Becker, Stephan Gschwind, Thomas Ohler, Bernhard Seeger, Peter Widmayer

In a variety of applications, weneedtokeep track of the development of a data set over time. For maintaining and querying these multiversion data e ciently, external storage structures are an...

Balanced Distributed Search Trees Do Not Exist (1995)

Brigitte Kröll, Z Urich, Theoretische Informatik, Departement Informatik, Departement Informatik, ...

This paper is a first step towards an understanding of the inherent limitations of distributed data structures. We propose a model of distributed search trees that is based on few natural...

Spatial Queries on Compressed Raster Images: How to get the Best of Both Worlds (1995)