Multicasting in the Hypercube, Chord and
Binomial Graphs ( with C. C. Cipriano),
Information Processing Letters, (to appear).
SP-Multicasting Trees(with C. C. Cipriano),
Proceedings of the 21th IASTED
International Conference on Parallel and Distributed Computing and
Systems PDCS '09 (6 pages).
We study the problem of finding an optimal ways to connect two disjoint
simple polygons that minimizes a given metric. For instance, the two
polygons represent islands to be connected by a bridge, the goal is to
identify a point on each of the two polygons as the end points of the
bridge, such that the longest distance from any point on one island
to any point on the other is minimized. In cases where it is possible
to have flyover-like bridges, the bridge is a straight line between its
two end points (immaterial of whether the two points are mutually
visible or not). In other cases, the bridge may need to stay outside
the interiors of the two polygons. E.g. if instead of a physical bridge,
we intend to find a route for a ferry that connects the two islands,
the route would need to stay within the water region that separates
the two islands. In the following two papers we present exact and
approximation algorithms to solve these two problems. Both the algorithms
and their analysis is complex. Other researchers working on this problem
include: Tan (Tokai), Tokuyama (Tohoku), Kim (Chung-Ang), Shin (KAIST), etc.
Exact and Approximation Algorithms for
finding the Optimal Bridge
Connecting Two Simple Polygons, (with A. M. Bhosle), International
Journal on Computational Geometry and Applications, Vol 15, No. 6,
pp. 609 - 630, Dec. 2005.
Finding Optimal Geodesic Bridges Between Two
Simple Polygons ( with A. Bhosle), submitted for possible publication.
The complexity of constructing an minimum total completion time for a
set of uniform tasks on a uniform processor system had been opened for
more than two decades. We developed a complex algorithm with an equally
complex correctness proof to solve this long-standing open problem.
The algorithm is based on solving a set of problems where the
ordering of the finish time of the tasks is known.
After a number of iterations our algorithm generates an optimal solution.
This work appears in
the following paper. Other researchers that worked on this problem include:
Coffman (Columbia), Lawler (Berkeley), Leung (NJIT), Pinedo (NYU), etc.
Minimizing Total Completion Time on Uniform
Processor Systems with Deadline Constraints,(with J. Leung and M. Pinedo),
Transactions on Algorithms, Vol. 2, No. 1, pp. 95 - 115, 2006.
We have developed centralized and distributed algorithms to compute
alternate paths required by some proactive recovery schemes for
handling transient failures. Our algorithms compute paths that avoid
a failed node or edge, and provides an alternate path to a
particular destination from an upstream neighbor of the failed node
or edge. All previous algorithms proposed for computing alternate
paths were centralized, and need complete information of the network
graph as input to the algorithm. Our centralized algorithms are faster
and generate better solutions than previous algorithms.
In addition, our algorithm can be made to run efficiently in a distributed
environment. The CV has
a list of conference presentations of this work.
Other researchers that worked on this problem include:
Widmayer (ETH Zurich), Nardelli (ETH Zurich), Slosier (Telstra), Latin (Telstra), etc.
Algorithms for Single Link Failure Recovery and
Related Problems, (with A. M. Bhosle), Journal of Graph Algorithms
and Applications, Vol. 8, No 3, pp 275 -- 294, 2004.
Distributed Algorithms for Computing Alternate
Paths Avoiding Failed Nodes and Links ( with A. Bhosle), submitted
for possible journal publication.
Given a rectangular boundary partitioned into rectangles, the
Minimum-Length Corridor problem consists of finding a corridor of least
total length. A corridor is a set of connected line segments, each of
which must lie along the line segments that form the rectangular
boundary and/or the boundary of the rectangles, and must include at
least one point from the boundary of every rectangle and from the
rectangular boundary. In our papers we established that this problem
as well as related ones are NP-hard and established a constant ratio
polynomial time approximation algorithms for this problem. Researchers
had been working on this problem for about a decade without success.
Our approximation algorithm is based on restriction and relaxation
techniques.
The
CV
has
a list of conference presentations of this work.
Ther researchers that worked on this problem include:
Bodlaender (Uthrect), Eppstein (UCI), Sitters (Germany), Katoh (Japan), etc.
Approximating Corridors and Tours via
Restriction and Relaxation Techniques, (with A. Gonzalez),
ACM Transactions on Algorithms, (to appear).
Complexity of the Minimum-Length Corridor
Problem, (with A. Gonzalez), Journal of Computational Geometry: Theory
and Applications, Vol. 37, No. 2, pp. 72 -- 103, 2007.
Given pairs of vertices and the goal is to find a path for each pair of
vertices so that all of the paths are pairwise node disjoint in a
hypercube. Furthermore each path must have length equal to the Hamming
distance between the pair of vertices it joins (we call these paths
shortest paths, because each path must be shortest one when ignoring all
other pairs and their paths). We also extended this work to the EDGE
disjoint case as well as to the grid (mesh) architecture. These
communication problems arise when executing algorithms in (hypercube
and mesh connected) parallel computer systems.
The main results are polynomial time algorithms for restricted versions
of the problem and then showing that the problems are NP-complete or
NP-hard even when the the vertices in each pair are near to each other.
The interesting point is that the hypercube NP-Completeness result hold
even when the total number of nodes in the hypercube is polynomially
related to the number of inputs to the problem. This was the first
result of this nature. For example, all the known results for problem
(A) above do not satisfy this property. I.e., the input and output size
is a small fraction of a huge hypercube. Our work has resulted in multiple
journal and conference presentations. The CV has a list of conference
presentations of this work. Other researchers working on this problem
include: van Leeuwen (Uthrect), Sudborough (UTD), Lubiw (Canada), Peng
(Japan), Latifi (UNLV), etc.
Pairwise Disjoint Shortest Paths in the n-Cube
and Related Problems,
(with D. Serena), Theoretical Computer Science, Vol 369, No. 1,
pp. 427 -- 435, 2006.
Complexity of the Pairwise Shortest Path Routing in the Grid, (with D. Serena), Theoretical Computer Science, Vol. 326, 1-3, pp. 155 -185, 2004.
n-Cube Network: Node Disjoint Shortest Paths
for Maximal Distance Pairs of Vertices, (with D. Serena),
Journal of Parallel Computing, Vol. 30, 8, pp. 973 -998, 2004.
The multimessage multicasting problem for parallel computers arises
when executing dynamic programming procedures or solving systems of
linear equations via iterative methods in parallel computers. The
parallel computer allows for message multicasting which means that
at any given time a processor may send to a subset of its neighbors
the same message, but the restrictions are that every processor may send
and receive at most one message at a time. This communication mode
is available in real parallel computers, and it models perfectly the
communications available in wireless and radio networks. This
communication mode is more flexible than the telephone mode (send
a message to one destination at a time) or broadcasting (send to all
neighbors). The problem is to construct a communication schedule with
minimum total communication time. I showed that the decision version
of this problem is NP-hard.
I have developed approximation algorithm for different variants of
the problem. The variants include message forwarding (sending messages
indirectly) and direct delivery of messages, on-line (distributed)
and off-line
construction of the schedules, fully connected machines and machines
connected by multistage interconnection networks, and so on. The main
contribution was to solve complex communication problems using a modern
communication model that is applicable, and more flexible than previous
ones. This work has also applications to radio and wireless networks
as well as in all-optical networks. All of this work appears in
single-author papers, and considers the problem from several points of
view.
The CV has a list of other journal and conference presentations of this work.
Other researchers working on this problem include:
Choi (Maryland), Hajek (UIUC), Rivera-Vega (Puerto Rico), Shen (Adelaide),
Hakimi (Northwestern), Coffman (Columbia), LaPaugh (Princeton), etc.
Complexity and Approximations for Multimessage
Multicasting, Journal
of Parallel and Distributed Computing, 55, pp. 215 -- 235, 1998
Simple Algorithms for MultiMessage Multicasting
with Forwarding,
Algorithmica, Vol. 29, pp. 511 -- 533, 2001.
Journal of Parallel Computing, Vol. 30, 8, pp. 973 -998, 2004.
Distributed Algorithms for Multimessage
Multicasting, Journal of Interconnection Networks,
Vol. 1, No. 4, Dec 2000, pp 303 -- 315.
Continuous Delivery Message Dissemination
Problems Under the Multicasting
Communication Mode, IEEE Transactions Transactions on Parallel and
Distributed Systems, Vol. 19, No. 8, pp. 1034 - 1043, 2008.
The following paper contains a summary of all of this work.
Message Dissemination Using Modern
Communication Primitives, Handbook of Parallel
Computing: Models, Algorithms, and Applications, Eds. J. Reif and S.
Rajasekaran, Chapman & Hall / CRC, Jan. 2008.
I have made other important contributions recently (see my CV), but I feel the above papers
are my most significant contributions.