Index Catalog // Carleton University Institutional Repository

External memory algorithms for outerplanar graphs

Resource Type:: Conference Proceeding
Creator:: Maheshwari, Anil and Zeh, Norbert
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 a2-separator of size 2 for a given outerplanar graph. Our algorithms take O(sort(N)) I/Os and can easily be improved to take O (perm (N)) I/Os, as all these problems have linear time solutions in internal memory. For BFS, DFS, and outerplanar embedding we show matching lower bounds.
Date Created:: 1999-01-01

An ϵ - Approximation algorithm for weighted shortest paths on polyhedral surfaces

Resource Type:: Conference Proceeding
Creator:: Maheshwari, Anil, Sack, Jörg-Rüdiger, Lanthier, Mark, and Aleksandrov, Lyudmil
Date Created:: 1998-01-01

I/O and space-efficient path traversal in planar graphs

Resource Type:: Conference Proceeding
Creator:: He, Meng, Dillabaugh, Craig, Zeh, Norbert, and Maheshwari, Anil
Date Created:: 2009-12-01

Succinct and I/O efficient data structures for traversal in trees

Resource Type:: Conference Proceeding
Creator:: Dillabaugh, Craig, He, Meng, and Maheshwari, Anil
Abstract:: We present two results for path traversal in trees, where the traversal is performed in an asymptotically optimal number of I/Os and the tree structure is represented succinctly. Our first result is for bottom-up traversal that starts with a node in the tree T and traverses a path to the root. For blocks of size B, a tree on N nodes, and for a path of length K, we design data structures that permit traversal of the bottom-up path in O(K/B) I/Os using only bits, for an arbitrarily selected constant, ε, where 0∈<∈ε<∈1. Our second result is for top-down traversal in binary trees. We store T using (3∈+∈q)N∈+∈o(N) bits, where q is the number of bits required to store a key, while top-down traversal can still be performed in an asymptotically optimal number of I/Os.
Date Created:: 2008-12-01

Computing the greedy spanner in near-quadratic time

Resource Type:: Conference Proceeding
Creator:: Bose, Prosenjit, Maheshwari, Anil, Carmi, Paz, Smid, Michiel, and Farshi, Mohammad
Abstract:: It is well-known that the greedy algorithm produces high quality spanners and therefore is used in several applications. However, for points in d-dimensional Euclidean space, the greedy algorithm has cubic running time. In this paper we present an algorithm that computes the greedy spanner (spanner computed by the greedy algorithm) for a set of n points from a metric space with bounded doubling dimension in time using space. Since the lower bound for computing such spanners is Ω(n 2), the time complexity of our algorithm is optimal to within a logarithmic factor.
Date Created:: 2008-10-27

Geometric spanners with small chromatic number

Resource Type:: Conference Proceeding
Creator:: Couture, Mathieu, Smid, Michiel, Maheshwari, Anil, Bose, Prosenjit, Carmi, Paz, and Zeh, Norbert
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 chromatic number at most k. We prove that t(2)∈=∈3, t(3)∈=∈2, , and give upper and lower bounds on t(k) for k∈>∈4. We also show that for any ε>∈0, there exists a (1∈+∈ε)t(k)-spanner for P that has O(|P|) edges and chromatic number at most k. Finally, we consider an on-line variant of the problem where the points of P are given one after another, and the color of a point must be assigned at the moment the point is given. In this setting, we prove that t(2)∈=∈3, , , and give upper and lower bounds on t(k) for k∈>∈4.
Date Created:: 2008-08-27

The discrete voronoi game in a simple polygon

Resource Type:: Conference Proceeding
Creator:: Smid, Michiel, Maheshwari, Anil, Das, Sandip, and Banik, Aritra
Abstract:: Let P be a simple polygon with m vertices and let be a set of n points in P. We consider the points of to be users. We consider a game with two players and. In this game, places a point facility inside P, after which places another point facility inside P. We say that a user is served by its nearest facility, where distances are measured by the geodesic distance in P. The objective of each player is to maximize the number of users they serve. We show that for any given placement of a facility by, an optimal placement for can be computed in O(m + n(logn + logm)) time. We also provide a polynomial-time algorithm for computing an optimal placement for.
Date Created:: 2013-10-08

An external memory data structure for shortest path queries

Resource Type:: Conference Proceeding
Creator:: Zeh, Norbert, Hutchinson, David, and Maheshwari, Anil
Abstract:: We present results related to satisfying shortest path queries on a planar graph stored in external memory. In particular, we show how to store rooted trees in external memory so that bottom-up paths can be traversed I/O-efficiently, and we present I/O-efficient algorithms for triangulating planar graphs and computing small separators of such graphs. Using these techniques, we can construct a data structure that allows for answering shortest path queries on a planar graph I/O-efficiently.
Date Created:: 1999-01-01

I/O-efficient shortest path queries in geometric spanners

Resource Type:: Conference Proceeding
Creator:: Smid, Michiel, Zeh, Norbert, and Maheshwari, Anil
Abstract:: We present I/O-efficient algorithms to construct planar Steiner spanners for point sets and sets of polygonal obstacles in the plane, and for constructing the “dumbbell” spanner of [6] for point sets in higher dimensions. As important ingredients to our algorithms, we present I/O efficient algorithms to color the vertices of a graph of bounded degree, answer binary search queries on topology buffer trees, and preprocess a rooted tree for answering prioritized ancestor queries.
Date Created:: 2001-01-01

Succinct orthogonal range search structures on a grid with applications to text indexing

Resource Type:: Conference Proceeding
Creator:: Bose, Prosenjit, Maheshwari, Anil, He, Meng, and Morin, Pat
Abstract:: We present a succinct representation of a set of n points on an n×n grid using bits to support orthogonal range counting in time, and range reporting in time, where k is the size of the output. This achieves an improvement on query time by a factor of upon the previous result of Mäkinen and Navarro [1], while using essentially the information-theoretic minimum space. Our data structure not only can be used as a key component in solutions to the general orthogonal range search problem to save storage cost, but also has applications in text indexing. In particular, we apply it to improve two previous space-efficient text indexes that support substring search [2] and position-restricted substring search [1]. We also use it to extend previous results on succinct representations of sequences of small integers, and to design succinct data structures supporting certain types of orthogonal range query in the plane.
Date Created:: 2009-09-14

External memory algorithms for outerplanar graphs

An ϵ - Approximation algorithm for weighted shortest paths on polyhedral surfaces

I/O and space-efficient path traversal in planar graphs

Succinct and I/O efficient data structures for traversal in trees

Computing the greedy spanner in near-quadratic time

Geometric spanners with small chromatic number

The discrete voronoi game in a simple polygon

An external memory data structure for shortest path queries

I/O-efficient shortest path queries in geometric spanners

Succinct orthogonal range search structures on a grid with applications to text indexing

Limit your search

Collection

Resource Type

Date Created

Creator

Language

Search Constraints

Search Results

Limit your search