Most Significant Recent Research Contributions

Teofilo F. Gonzalez

  • Research Areas
  • (A) Multicasting in the Hypercube, Chord and Binomial Graphs
    (B) Algorithms for Bridge Problems
    (C) Scheduling Uniform Processors with Deadlines
    (D) Finding Recovery Paths in the Presence of Transient Failures
    (E) Corridor Problems
    (F) Pairwise Disjoint Paths in the Hypercube
    (E) Multimessage Multicasting

  • Research Accomplishments
  • (A) Multicasting in the Hypercube, Chord and Binomial Graphs

    For several decades the problem of multicasting in the hypercube to minimize the total communication time has been studied. This problem is related to to finding minimal Phylogenies in Bioinformatics. In this series of papers we revisited the complexity of generating optimal and near-optimal solutions to this problem and its variations, where each message arrives to its destination in optimal time and the secondary measure is to minimize the total communication time. Our main results are simple NP-complete reductions for this problems and efficient algorithms to generate the best-known suboptimal solutions for some of these problems. We also extend our results to close variants of the hypercube that include the Chord and the Binomial Graph (BNG) Network by developing a general reduction technique. Other researchers working on these problems include: Graham (UCSD), Fujita (Hiroshima), Li (Michigan State), Dongarra (Tenn.), Bosilica (Tenn.), etc.

    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).

    (B) Algorithms for Bridge Problems

    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.

    (C) Scheduling on Uniform Processors with Deadlines

    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.

    (D) Finding Recovery Paths in the Presence of Transient Failures

    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.

    (E) Corridor Problems

    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.

    (F) Pairwise Disjoint Paths in the Hypercube

    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.

    (G) Multimessage Multicasting

    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.