Geometric Spanners With Small Chromatic Number (2007)
Bose, Prosenjit, Carmi, Paz, Couture, Mathieu, Maheshwari, Anil, Smid, Michiel, Zeh, Norbert
Given an integer $k \geq 2$, we consider the problem of computing the smallest real number $t(k)$ such that for each set $P$ of points in the plane, there exists a $t(k)$-spanner for $P$ that has...
Approximating Geometric Bottleneck Shortest Paths (2004)
Anil Maheshwari, Giri Narasimhan, Michiel Smid, Norbert Zeh
In a geometric bottleneck shortest path problem, we are given a set S of n points in the plane, and want to answer queries of the following type: Given two points p and q of S and a real number L,...
Brodal, Gerth Stølting, Fagerberg, Rolf, Meyer, Ulrich, Zeh, Norbert, Hagerup, Torben, Katajainen, Jyrki
Journal of Graph Algorithms and Applications (2003)
Lars Arge, Ulrich Meyer, Norbert Zeh
Even though a large number of I/O-e#cient graph algorithms have been developed, a number of fundamental problems still remain open. For example, no space- and I/O-e#cient algorithms are known for...
I/O-Efficient Topological Sorting of Planar DAGs (2003)
Lars Arge, Laura Toma, Norbert Zeh
We present algorithms that solve a number of fundamental problems on planar directed graphs (planar digraphs) in O(sort(N)) I/Os, where sort(N) is the number of I/Os needed to sort N elements. The...
Approximating Geometric Bottleneck Shortest Paths (2003)
Anil Maheshwari, Giri Narasimhan, Michiel Smid, Norbert Zeh
In a geometric bottleneck shortest path problem, we are given a set S of n points in the plane, and want to answer queries of the following type: Given two points p and q of S and a real number L,...
I/O-Efficient Undirected Shortest Paths (2003)
Meyer, Ulrich, Zeh, Norbert, Di Battista, Giuseppe, Zwick, Uri
On Reverse Nearest Neighbor Queries (2002)
In this paper, we discuss static and dynamic data structures for answering reverse nearest neighbor queries in two dimensions.
I/O-Efficient Batched Range Counting and Its Applications to Proximity Problems (2001)
We present an algorithm to answer a set Q of range counting queries over a point set P in d dimensions. The algorithm takes O sort(jP j + jQj) + (jP j+jQj)(jP j) DB log d 1 M=B jP j+jQj B 1 I/Os and...
I/O-Optimal Planar Embedding Using Graph Separators (2001)
We present a new algorithm to test whether a given graph G is planar and to compute a planar embedding G of G if such an embedding exists. Our algorithm utilizes a fundamentally new approach based on...
I/O-Efficient Planar Separators and Applications (2001)
We present a new algorithm to compute a subset S of vertices of a planar graph G whose removal partitions G into O(N=h) subgraphs of size O(h) and with boundary size O( p h) each. The size of S is...
On External-Memory Planar Depth First Search (2001)
Lars Arge, Ulrich Meyer, Laura Toma, Norbert Zeh
Even though a large number of I/O-efficient graph algorithms have been developed, a number of fundamental problems still remain open. For example, no space- and I/O-efficient algorithms are known for...
I/O-Efficient Algorithms for Bounded Treewidth Graphs (2001)
We present an I/O-efficient algorithm for the single source shortest path (SSSP) problem for graphs of bounded treewidth. For sparse graphs in general SSSP seems to be extremely hard to solve. We...
I/O-Efficient Well-Separated Pair Decomposition and its Applications (2001)
Callahan and Kosaraju [7] introduced the well separated pair decomposition (WSPD) data structure as a mechanism for solving a number of problems on point sets in d-dimensional space. We present an...
I/O-Efficient Algorithms for Graphs of Bounded Treewidth (2001)
We present I/O-ecient algorithms for the single source shortest path problem and NP-hard problems on graphs of bounded treewidth. The main step in these algorithms is a method to compute a...
I/O-Efficient Well-Separated Pair Decomposition and its Applications (2000)
Sathish Govindarajan, Anil Maheshwari, Norbert Zeh
this paper, we describe an I/O efficient algorithm for computing the well-separated pair decomposition of P . Using the well-separated pair decomposition, we develop I/O efficient algorithms to solve...
An External-Memory Data Structure for Shortest Path Queries (1999)
David Hutchinson, Anil Maheshwari, Norbert Zeh
In this paper, we present results related to satisfying shortest path queries on a planar graph stored in external memory. N denotes the total number of vertices and edges in the graph and sort(N)...