Boundary-Optimal Triangulation Flooding ⋆ (2008)
Richard J. Nowakowski, Norbert Zeh
Abstract. Given a planar triangulation all of whose faces are initially white, we study the problem of colouring the faces black one by one so that the boundary between black and white faces as well...
We present I/O-efficient algorithms for computing optimal separator partitions of planar graphs. Our main result shows that, given a planar graph G with N vertices and an integer r> 0, a vertex...
I/O-Efficient Well-Separated Pair Decomposition and its Applications (Extended Abstract) (2007)
Satish Govindarajan, Tamas Lukovszki, Anil Maheshwari, Norbert Zeh
) Sathish Govindarajan 1 , Tamas Lukovszki 2 , Anil Maheshwari 3 , and Norbert Zeh 3 1 Duke University, gsat@cs.duke.edu 2 University of Paderborn, Heinz-Nixdorf-Institut, tamas@hni.upb.de 3 Carleton...
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-Ecient Algorithms for Graphs of Bounded Treewidth (2007)
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...
Approximating Geometric Bottleneck Shortest Paths (2007)
Prosenjit Bose, 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,...
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...
Geometric spanners with small chromatic number (2007)
Prosenjit Bose, Paz Carmi, Mathieu Couture, Anil Maheshwari, Michiel Smid, Norbert Zeh
Abstract. Given an integer k ≥ 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...
Geometric Spanners With (2007)
Small Chromatic Number, Anil Maheshwari, Michiel Smid, Norbert Zeh
Given an integer k ≥ 2, we consider the problem of computing the smallest real number t(k) such that for each set P of points in the plane, a t(k)-spanner for P exists that has O(|P |) edges and...
I/O-efficient hierarchical watershed decomposition of grid terrain models (2006)
Lars Arge, Andrew Danner, Herman Haverkort, Norbert Zeh
Summary. Recent progress in remote sensing has made massive amounts of high resolution terrain data readily available. Often the data is distributed as regular grid terrain models where each grid...
I/O-Efficient Undirected Shortest Paths with Unbounded Edge Lengths (2006)
Meyer, Ulrich, Zeh, Norbert, Azar, Yossi, Erlebach, Thomas
We show how to compute single-source shortest paths in undirected graphs with non-negative edge lengths in I/Os, where n is the number of vertices, m is the number of edges, B is the disk block size,...
Brodal, Gerth Stølting, Fagerberg, Rolf, Meyer, Ulrich, Zeh, Norbert, Hagerup, Torben, Katajainen, Jyrki
Gerth Sto/lting Brodal, Rolf Fagerberg, Ulrich Meyer, Norbert Zeh
Abstract. We present improved cache-oblivious data structures and algorithms for breadth-first search and the single-source shortest path problem on undirected graphs with non-negative edge weights....
Gerth Sto/lting Brodal, Rolf Fagerberg, Ulrich Meyer, Norbert Zeh
Abstract. We present improved cache-oblivious data structures and algorithms for breadth-first search and the single-source shortest path problem on undirected graphs with non-negative edge weights....
Gerth Stølting Brodal, Rolf Fagerberg, Ulrich Meyer, Norbert Zeh
of all or part of this workis permitted for educational or research use on condition that this copyright notice isincluded in any copy. See back inner page for a list of recent BRICS Report Series...
Gerth Stølting Brodal, Rolf Fagerberg, Ulrich Meyer, Norbert Zeh
Abstract. We present improved cache-oblivious data structures and algorithms for breadth-first search and the single-source shortest path problem on undirected graphs with non-negative edge weights....
Copyright C, Gerth Stølting Brodal, Gerth Stølting Brodal, Gerth Stølting Brodal, Rolf Fagerberg, Rolf Fagerberg, ...
We present improved cache-oblivious data structures and algorithms for breadth-first search (BFS) on undirected graphs and the single-source shortest path (SSSP) problem on undirected graphs with...
Copyright C, Gerth Stølting Brodal, Gerth Stølting Brodal, Gerth Stølting Brodal, Rolf Fagerberg, Rolf Fagerberg, ...
Reproduction of all or part of this work is permitted for educational or research use on condition that this copyright notice is included in any copy. See back inner page for a list of recent BRICS...
Approximating Geometric Bottleneck Shortest Paths (2004)
Prosenjit Bose, 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,...
Gerth Stølting Brodal, Rolf Fagerberg, Ulrich Meyer, Norbert Zeh
Abstract. We present improved cache-oblivious data structures and algorithms for breadth-first search and the single-source shortest path problem on undirected graphs with non-negative edge weights....
Brodal, Gerth Stølting, Fagerberg, Rolf, Meyer, Ulrich, Zeh, Norbert, Hagerup, Torben, Katajainen, Jyrki
I/O-Efficient Undirected Shortest Paths (2003)
Meyer, Ulrich, Zeh, Norbert, Di Battista, Giuseppe, Zwick, Uri
I/O-efficient undirected shortest paths (2003)
Abstract. We present an I/O-efficient algorithm for the single-source shortest path problem on undirected graphs G =(V,E). Our algorithm performs O ( � (VE/B) log 2 (W/w) + sort(V + E) log...
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...
Connectivity of graphs under edge flips (2003)
We study the following problem: Given a set V of n vertices and a set E of m edge pairs, we define a graph family G(V, E) as the set of graphs that have vertex set V and contain exactly one edge from...
On External-Memory Planar Depth-First Search (2003)
Lars Arge, Ulrich Meyer, Laura Toma, 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 undirected shortest paths (2003)
Abstract. We show how to compute single-source shortest paths in undirected graphs with non-negative edge lengths in O ( p nm/B log n + MST (n, m)) I/Os, where n is the number of vertices, m is the...
I/O-efficient undirected shortest paths (2003)
Abstract. We present an I/O-efficient algorithm for the single-source shortest path problem on undirected graphs G = (V, E). Our algorithm performs O ( p (V E/B) log 2 (W/w) + sort(V + E) log log(V...
I/O-efficient undirected shortest paths (2003)
Ulrich Meyer, Ulrich Meyer, Norbert Zeh, Norbert Zeh
Abstract. We present an algorithm for computing single-source shortest paths in undirected graphs with non-negative edge weights in O ( � nm/Blogn + MST(n,m)) I/Os, where n is the number of...
On Reverse Nearest Neighbor Queries (2002)
Extended Anil, Anil Maheshwari, Norbert Zeh
In this paper, we discuss static and dynamic data structures for answering reverse nearest neighbor queries in two dimensions.
On finding minimum deadly sets for directed networks (2001)
Norbert Zeh, Lambda Nicola Santoro\lambda
Abstract Given a set S of elements in a directed network that are initially faulty, an element becomes (functionally)faulty if all its in-neighbors or all its out-neighbors are (functionally) faulty....
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 batched range counting and its applications to proximity problems (2001)
Abstract. 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
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
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 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 ( √ h) each. The size of S is...
On finding minimum deadly sets for directed networks (2001)
Given a set S of elements in a directed network that are initially faulty, an element becomes (functionally) faulty if all its in-neighbors or all its outneighbors are (functionally) faulty. A set S...
I/O-Optimal Algorithms for Outerplanar Graphs (2001)
We present linear-I/O algorithms for fundamental graph problems on embedded outerplanar graphs. We show that breadth-first search, depth-first search, single-source shortest paths, triangulation, and...
I/O-efficient well-separated pair decomposition and its applications (2000)
Sathish Govindarajan, Tamás Lukovszki, Anil Maheshwari, Norbert Zeh
Abstract. We present an external memory algorithm to compute a well-separated pair decomposition (WSPD) of a given point set P in £ d in O ¤ sort ¤ N¥¦ ¥ I/Os using O ¤ N § B ¥ blocks of...
I/O-efficient well-separated pair decomposition and its applications (2000)
Sathish Govindarajan, Anil Maheshwari, Norbert Zeh
Data sets of many modern applications are too large to fit into main memory, and must reside on disk. It has been observed that the Input/Output (I/O) communication between internal memory and disk...
I/O-efficient well-separated pair decomposition and its applications (2000)
Sathish Govindarajan, Tamás Lukovszki, Anil Maheshwari, Norbert Zeh
Abstract. We present an external memory algorithm to compute a well-separated pair decomposition (WSPD) of a given point set P in £ d in O ¤ sort ¤ N¥¦ ¥ I/Os using O ¤ N § B ¥ blocks of...
I/O-efficient well-separated pair decomposition and its applications (2000)
Sathish Govindarajan, Tamás Lukovszki, Anil Maheshwari, Norbert Zeh
Abstract. We present an external memory algorithm to compute a well-separated pair decomposition (WSPD) of a given point set P in £ d in O ¤ sort ¤ N¥¦ ¥ I/Os using O ¤ N § B ¥ blocks of...
External memory algorithms for outerplanar graphs (1999)
Abstract. We present external memory algorithms for outerplanarity testing, embedding outerplanar graphs, breadth-first search (BFS) and depth-first search (DFS) in outerplanar graphs, and finding a 2
An External-Memory Data Structure for Shortest Path Queries (1999)
David Hutchinson, Anil Maheshwari, Norbert Zeh, N That Uses
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)...
An external-memory data structure for shortest path queries (1998)
Von Norbert Zeh, Fakult"at Mathematik Informatik, Norbert Zeh, Diplomarbeit Norbert Zeh
ii An External-Memory Data Structure for Shortest Path Queries