|
Imran A. Pirwani
The following is a list of my papers and talks: |
|
|
Conference Publications: Toggle Abstracts |
|
|
6. |
Good Quality Virtual Realization of Unit Ball Graphs Toggle Abstract Given a unit disk graph (UDG) with only connectivity information (no geometric model), we compute an approximate embedding into the Euclidean plane of the graph (a realization) that seeks to minimize the ratio of the longest edge and the shortest non-edge. The approximation ratio achieved is log2.5n; the construction is combinatorial. This is an improvement over the best known approximation of log3n times lower order terms which requires solving an LP with exponentially many constraints. We also provide a (k, &radiclog n)-volume respecting embedding (in O(log3n) dimensions) of a growth restricted graph which corresponds to a clique partition of the given UBG. We also provide an O(1) quality embedding of the UBG in O(1) dimensions. The key structure (the cluster graph) is based upon a partition of the neighborhood of a vertex into O(1) cliques without any geometry. A consequence of this is a first polynomial time (computational complexity of each node), fully distributed O(1) factor approximation to the minimum clique cover of a UDG without geometry in deterministic O(log Δ log* n) rounds or O(log log n log* n) rounds w.h.p (due to a recent result). |
|
5. |
Topology Control and Geographic Routing in Realistic Wireless Networks Toggle Abstract Given a d-QUDG, d > 1/&radic2, we show how to compute a sparse, O(1)-spanner both in Euclidean and hop distance; the protocol runs in O(1) rounds of distributed computation. The output permits memoryless (geographic) routing with guaranteed delivery. The construction uses the idea of virtual nodes placed at edge crossings (which can be locally detected) such that a proxy for it is nearby and each proxy is responsible for a constant number of virtual nodes. This provides for a cheap way of planarizing non-planar graphs permitting geographic routing. |
|
4. |
Energy Conservation in Wireless Sensor Networks via Domatic Partitions Toggle Abstract Typical wireless sensor network deployment strategies suggest that these networks are quite dense. Hence, the network has plenty of redundancy with respect to coverage in a typical application. Exploitation of such redundancies can lead to great energy savings. We apply the domatic partition problem on various classes of graphs that are used to model wireless sensor networks. We present three distributed algorithms that run in O(1), O(log* n), O(log Δ log* n) rounds under successively weaker assumptions. Δ denotes the maximum degree in the graph.) |
|
3. |
Oriented Edge Colorings and Link Scheduling in Sensor Networks Toggle Abstract For an acyclic network, we present a distributed algorithm that computes a TDMA slot assignment using ((1+&epsilon) 2 * Δ ) slots in O(polylog( n )) rounds, with high probability. (Δ denotes the maximum degree in the graph.) |
|
2. |
Introduction to the Non-rigid Image Registration Evaluation Project (NIREP) Toggle Abstract Non-rigid image registration (NIR) is an important tool that allows for morphological comparisons in the presence or anatomical variations. While many NIR algorithms have been devised, they are difficult to evaluate in the absence of point-wise inter-image correspondence. We provide a framework that allows for evaluation of these algorithms. |
|
1. |
A Composite Stabilizing Data Structure Toggle Abstract We present a composite data structure that is both available and stabilizing. It is stabilizing in the sense that it is resilient to transient faults occurring in that over the course of time as the data structure is operated upon, it corrects itself. It is available in the sense that while it is possibly in an illegitimate state, it is available to operations and a successful operation is guaranteed to change the state of the data structure in an expected manner. |
|
Reports and Manuscripts: |
|
|
2. |
On k-domination of Graphs
|
|
1. |
A Self Stabilizing Algorithm for a Weaker form of Distributed Mutual Exclusion
|
|
Talks |
|
|
1. |
Extending the Lifetime of Wireless Networks while Ensuring Coverage |