Main research contributions (A) The most recent work (with Serena) is on the problem of finding pairwise node disjoint shortest paths for pairs of vertices in the hypercube. You are 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. 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. This work was presented at conferences (A-57 and A-59) and has been submitted for journal publication. The main contribution was in establishing the computational complexity of these problems. (B) The papers (A-48, A-51, A-54) present my results for the multimessage multicasting problem for parallel computers. This problem 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 problem is NP-hard. And 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 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. (C) Papers (A-30, A-15 and A-32, by Gonzalez, Razzazi, Shing and Zheng) deal with the problem of partitioning a rectangle with interior points into rectangles so that the length of the partitioning line segments is least possible as well as the generalization of this problem to multidimensional space. This problem has applications in VLSI routing and our contribution was developing provably good solutions to this problem. The three different algorithm take increasing more computation time, but as the time complexity increases the solutions generated are provably better. (D) One of the basic problems in VLSI routing is the two-terminal net routing around a rectangle to minimize the area of the smallest rectangle enclosing the wire layout. Gonzalez and Lee (A-10) presented the first linear time algorithm for this problem. This is a simple and elegant algorithm with a complex correctness proof. The main idea was to reduce the problem to one of four problems, each of which can be solved by a greedy technique. Another basic routing problem in VLSI is the two-terminal channel routing problem. Gonzalez and Zheng (A-31) developed a simple technique to solve this problem. The proof of correctness is also simple and elegant. These two problems are classic VLSI routing problems and were among the first problems studied when VLSI became a fashionable area for algorithmic research. (E) A problem which has encountered many applications is that of clustering a set of points into a given number of clusters so that the farthest distance between two points in the same cluster is minimized. I developed an efficient approximation algorithm for this problem and showed that it is best possible unless P = NP. The algorithm has found applications in many different areas, e.g., color quantization, databases, web applications, etc. The results provide a best possible solution. This result appears in the single-author paper labeled P-25. (F) Gonzalez and Sahni (P-3) are the originators of the open shop scheduling problem. They defined the open shop scheduling problem (P-3) and developed an efficient algorithm for preemptive scheduling independent jobs. The problem has found applications in telecommunications, communication networks, parallel algorithms, and scheduling theory, etc. Their original algorithm has not be improved, except when there is a constant number of machines or jobs (P-11). Other scheduling work includes: scheduling jobs under tree-like precedence constraints on identical machines (Gonzalez and Johnson), non-preemptive uniform processor scheduling, and flow shop and job shop scheduling. The work was innovative because it introduced new techniques to solve scheduling problems as well as a new class of scheduling problems. (G) Another well-know result by Gonzalez and Sahni, was establishing (for the first time) that for a class of problems the finding an approximate solution to a problem as difficult (computationally) as generating the optimal one (P-2). This work has received numerous citations. ----- There is also other work, but I feel the above one is the most important one. ----- ---- Sample Publications ---- (P-2) P-Complete Approximation Problems, with S. Sahni, {\em Journal of the Association for Computing Machinery} Vol. 23, No. 3, pp. 555 -- 565, 1976. (P-3) Open Shop Scheduling to Minimize Finish Time, with S. Sahni, {\em Journal of the Association for Computing Machinery} Vol. 23, No. 4, pp. 665 -- 679, 1976. (P-11) A Note on Open Shop Preemptive Schedules, {\em IEEE Transactions on Computers,} Vol. C-28, No. 10, pp. 782 -- 786, 1979. (P-25) Clustering to Minimize the Maximum Inter-Cluster Distance, {\em Journal of Theoretical Computer Science,} No. 38, pp. 293 -- 306, 1985. (A-10) A Linear Time Algorithm for Optimal Wiring Around a Rectangle, with S. L. Lee, {\em Journal of the Association for Computing Machinery,} Vol. 35, No. 4, pp. 810 -- 832, 1988. (A-15) Approximation Algorithms for Partitioning Rectilinear Polygons with Interior Points (with S. Q. Zheng), {\em Algorithmica,} Vol. 5, pp. 11 -- 42, 1990. (A-30) An Efficient Divide-and-Conquer Approximation Algorithm for Partitioning D--Boxes, with M. Razzazi, and S. Q. Zheng, {\em International Journal on Computational Geometry and Applications,} Vol. 3, No. 4, pp. 417 -- 428, 1993. (A-31) Single Phase Three--Layer Channel Routing Algorithms, with S. Q. Zheng, {\em INTEGRATION, the VLSI Journal,} 17, pp. 141 -- 151, 1994. (A-32) On Optimal Guillotine Partitions Approximating Hyperrectangular Partitions, with M. Razzazi, M. Shing and S. Q. Zheng, {\em Computational Geometry: Theory and Applications,} Vol. 4, pp. 1 -- 11, 1994. (A-34) LP--Free Approximation Algorithm for the Minimum Weight Vertex Cover Problem, {\em Information Processing Letters,} 54, pp. 129 -- 131, 1995. (A-48) Complexity and Approximations for Multimessage Multicasting, {\it Journal of Parallel and Distributed Computing,} 55, pp. 215 -- 235, 1998 (A-51) Simple Algorithms for the On-Line Multidimensional Problem and Related Problems, {\it Algorithmica,} Vol 28, pp. 255 -- 267, 2000. (A-54) Simple Algorithms for MultiMessage Multicasting with Forwarding, {\it Algorithmica,} Vol. 29, pp. 511 -- 533, 2001. (A-57) Node Disjoint Shortest Paths for Pairs of Vertices in an $n$-Cube Network, (with F. D. Serena), Proceedings of the Conference on Parallel and Distributed Computing and Systems PDCS'01, Anaheim, CA, 278 -- 282, 2001. (A-59) $n$-Cube Search Algorithm for Finding $(n-1)$-Pairwise Node Disjoint Shortest Paths, (with F. D. Serena), Proceedings of the International Conference on Communications in Computing CIC'02, Las Vegas, Nv, pp. 19 -- 25, 2002. (A-60) Complexity of $k$-Pairwise Disjoint Shortest Paths in the Undirected Hypercubic Network and Related Problems, (with F. D. Serena), Proceedings of the Conference on Parallel and Distributed Computing and Systems PDCS '02, MIT, Cambridge, Ma, pp. 61 -- 66, 2002. ----- ----