Graph Algorithms Publications

Multicasting in the Hypercube, Chord and Binomial Graphs ( with Christopher C. Cipriano), submitted for possible journal publication.

Finding Optimal Geodesic Bridges Between Two Simple Polygons ( with A. Bhosle), submitted for possible journal publication.

Distributed Algorithms for Computing Alternate Paths Avoiding Failed Nodes and Links ( with A. Bhosle), submitted for possible journal publication.

Improved Algorithms for Constructing Hypercube SP-Multicasting Trees (with C. Cipriano), Proceedings of the 21th IASTED International Conference on Parallel and Distributed Computing and Systems PDCS '09 (6 pages).

Distributed Algorithms for Computing Alternate Paths Avoiding Failed Nodes and Links, (with A. Bhosle), Proceedings of the 21th IASTED International Conference on Parallel and Distributed Computing and Systems PDCS '09.

Interconnecting Rectangular Areas by Corridors and Tours (with A. Gonzalez), Proceedings of the SIEEEM, Monterrey, Oct. 2008.

Wavelength Assignment in Multifiber Optical Star Networks under the Multicasting Communication Mode, (with R. Brandt), Journal of Interconnection Networks, Vol. 6, No. 5, pp. 383 - 406, 2005.

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.

Replacement Paths for Pairs of Shortest Path Edges in Directed Graphs, (with A. M. Bhosle), Proceedings of the 16th IASTED International Conference on Parallel and Distributed Computing and Systems PDCS '04, (2004), MIT Cambridge MA, 94--99.

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.

Complexity of the Pairwise Shortest Path Routing in the Grid, (with D. Serena), Theoretical Computer Science, Vol. 326, 1-3, pp. 155 -185, 2004.

Open Shop Scheduling," in Handbook of Scheduling: Algorithms, Models, and Performance Analysis, Ed. Y. J.-T. Leung, Chapter 6, Part II, Chapman & Hall / CRC, 2004.

An Efficient Algorithm for Gossiping in the Multicasting Communication Environment," IEEE Transactions on Parallel and Distributed Systems, Vol 14, No. 7, pp. 701 -708, 2003.

Multicasting using WDM in Multifiber Optical Star Networks, (with R. Brandt), Proceedings of the 15th IASTED International Conference on Parallel and Distributed Computing and Systems PDCS '03, (2003), Marina Del Rey, CA, 56 -- 61.

Efficient Algorithms for Single Link Failure Recovery and Its Application to ATM Networks, (with A. M. Bhosle), Proceedings of the 15th IASTED International Conference on Parallel and Distributed Computing and Systems PDCS '03, (2003), Marina Del Rey, CA, 87 -- 92.

Complexity of k-Pairwise Disjoint Shortest Paths in the Undirected Hypercubic Network and Related Problems, (with F. D. Serena) Proceedings of the 14th IASTED International Conference on Parallel and Distributed Computing and Systems PDCS '02, (2002), MIT Cambridge, MA, 61 -- 66.

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, (2002), Las Vegas, NV, 19 -- 25.

On Solving Multimessage Multicasting Problems, International Journal of Foundations of Computer Science, Special Issue on Scheduling - Theory and Applications, Vol. 12, No. 6, pp. 791 -- 808, 2001.

Simple Algorithms for MultiMessage Multicasting with Forwarding, Algorithmica, Vol. 29, 2001, pp. 511 -- 533.

Minimum-Energy Broadcast in Simple Graphs with Limited Node Power, (with O. Egecioglu) Proceedings of the 13th IASTED International Conference on Parallel and Distributed Computing and Systems PDCS '01, (2001), Anaheim, CA, 278 -- 282.

Node Disjoint Shortest Paths for Pairs of Vertices in an n-Cube Network, (with F. D. Serena) Proceedings of the 13th IASTED International Conference on Parallel and Distributed Computing and Systems PDCS '01, (2001), Anaheim, CA, 278 -- 282.

Gossiping in the Multicasting Communication Environment, Proceedings of the International Parallel and Distributed Processing Symposium, IPDPS 2001, (6 pages).

Distributed Algorithms for Multimessage Multicasting, Journal of Interconnection Networks, Vol. 1, No. 4, Dec 2000, pp 303 -- 315.

Gossiping with Multicasting Communication Primitives, Proceedings of the 12th IASTED International Conference on Parallel and Distributed Computing and Systems PDCS '00, (2000), Las Vegas, NV, Vol. II, 768 -- 773.

Multimessage Multicasting with Bounded Number of Destinations, Proceedings of the 11th IASTED International Conference on Parallel and Distributed Computing and Systems PDCS '99, (1999), Cambridge, MA, 495 -- 500.

Distributed Multimessage Multicasting, Proceedings of the Thirteen International Conference On Systems Engineering, pp. CS-43 -- CS-48, Las Vegas, Nevada, August 1999.

Complexity and Approximations for Multimessage Multicasting, Journal of Parallel and Distributed Computing, 55, 1998, 215 -- 235.

Bounded Fan-Out MultiMessage Multicasting, Nordic Journal on Computing, Vol. 5, 1998, 196 -- 213.

Improved Approximation Algorithms for Embedding Hypergraphs in a Cycle, Information Processing Letters, Vol. 67, 1998, 267 -- 271.

Self--Stabilizing Algorithms for Tree Metrics (with A. K. Datta, and V. Thiagarajan), Parallel Processing Letters, Vol. 8, No. 1, World Scientific, March 1998. p.121-33.

Balanced Min and Max Cuts Under the Triangle Inequality, (with T. Murayama), UCSB Department of Computer Science, Technical Report TRCS--98--24, October 1998.

Algorithms for MultiMessage Multicasting With Forwarding, Proceedings of the Tenth ISCA International Conference on Parallel and Distributed Computing Systems PDCS '97, pp. 372 -- 377, New Orleans, LA, 1997.

MultiMessage Multicasting: Complexity and Approximations, Proceedings of the 30th Hawaii International Conference on System Sciences (HICSS), (1997), vol.1, pp. 211 -- 220, Nominated for the Best Paper Award in the Software Technology Track.

A Computationally Intractable Problem on Simplicial Complexes, (with O. Egecioglu), Computational Geometry: Theory and Applications, Vol. 6, No. 2, 1996, pp. 85 -- 98.

Improved MultiMessage Multicasting Approximation Algorithms, Proceedings of the Ninth International Conference on Parallel and Distributed Computing Systems PDCS '96, pp. 456 -- 461, Dijon, France, September 1996.

MultiMessage Multicasting, Proceedings of the Third International Workshop on Parallel Algorithms for Irregularly Structured Problems (Irregular'96), Lecture Notes in Computer Science (1117), Springer, (1996), pp. 217 -- 228.

Complexity Aspects of Two--Dimensional Data Compression, (with H. Bodlaender and T. Kloks), Nordic Journal on Computing, Vol. 4, No. 2, 1995, pp. 462 -- 495.

Self--Stabilizing Algorithms for Tree Metrics (with V. Thiagarajan, and A. K. Datta), Proceedings of the First International Conference on Algorithms and Architectures for Parallel Processing (ICA3PP--95), Vol. 1, pp 471 -- 478, Australia, 1995.

LP--Free Approximation Algorithm for the Minimum Weight Vertex Cover Problem, Information Processing Letters, Vol. 54, No. 3, 1995, 129 -- 131.

A Computationally Intractable Problem of Simplicial Complexes, (with O. Egecioglu), 6th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC/SFCA '94), DIMACS, May 1994. Also in Seventh SIAM Conference on Discrete Mathematics, Albuquerque NM, June 22--25, 1994.

Approximation Algorithms, Keynote Address, Ninth International Conference On Systems Engineering, Las Vegas, Nevada, July 1993.

Algorithms for a Class of Min--Cut and Max--Cut Problems, (with T. Murayama), Proceedings of the Third Annual International Symposium on Algorithms and Computation, Lecture Notes in Computer Science #650, Springer--Verlag, December 1992, pp. 97 -- 105.

Complexity Aspects of Map Compression, (with H. Bodlaender and T. Kloks), Proceedings of the Data Compression Conference, April 1991, pp. 287 -- 296.

Complexity of Data Compression for Colored Maps, (with H. Bodlaender and T. Kloks), ALCOM Workshop on Data Structures, Graph Algorithms, and Computational Complexity, Berlin, Germany, October 1990.

Clustering to Minimize the Maximum Inter--Cluster Distance, Journal of Theoretical Computer Science, No. 38, October 1985, pp. 293 -- 306.

On the Computational Complexity of Path Covering Problems, (with S. Ntafos), Journal of Computer and Systems Sciences, Vol. 29, No. 1, October 1984, pp. 225 -- 342.

Optimal and Near--Optimal Routing Around a Rectangle, (with S. L. Lee), ORSA/TIMS National Joint Meeting, Dallas Texas, November 1984.

Approximation Algorithms for PLA Folding, Technical Report #128, The University of Texas at Dallas, March 1983.

Evaluation of Arithmetic Expressions with Algebraic Identities, (with J. JaJa), SIAM Journal on Computing, Vol. 11, No. 4, November 1982, pp. 633 -- 662.

On the Computational Complexity of Clustering and Related Problems, Systems Modeling and Optimization, Proceedings of the 10th IFIP Conference on Systems Modeling and Optimization, Lecture Notes in Control and Information Sciences #38, Springer--Verlag, August 1981, pp. 174 -- 182.

A Note on Open Shop Preemptive Schedules, IEEE Transactions on Computers, Vol. C--28, No. 10, October 1979, pp. 782 -- 786.

Minimizing the Average Flow Time on Open Shops, XXIV International Meeting of the Institute of Management Science, Honolulu, Hawaii, June 1979.

Open Shop Scheduling to Minimize Finish Time, (with S. Sahni), Journal of the Association for Computing Machinery, Vol. 23, No. 4, October 1976, pp. 665 -- 679.

P--Complete Approximation Problems, (with S. Sahni), Journal of the Association for Computing Machinery, Vol. 23, No. 3, July 1976, pp. 555 -- 565.