NP-Completeness Publications

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

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.

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.

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.

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.

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.

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

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.

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.

Pin Redistribution Problem for Multi--Chip Modules: Algorithms and Complexity, (with D. Chang), International Journal of High Speed Electronics and Systems, Special Issue on High Performance CAD for Packaging and Multi--Chip Modules, Vol. 6, No. 3, 1995, pp, 459 -- 475. Also appears in High Performance Design Automation for Multi--Chip Modules and Packages, Selected Topics in Electronics and Systems -- Vol. 5, Edited by J. D. Cho, and P. D. Franzon, World Scientific Publishing Co., 1996 (IBSN 981--02--2307--2).

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.

A Flow Based Approach to the Pin Redistribution Problem for Multi--Chip Modules, (with D. Chang, and O. H. Ibarra), Proceedings of the GLS--VLSI '94 Conference, March 1994, pp. 114 -- 119.

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.

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.

An Approximation Algorithm for the Multi--Via Assignment Problem, IEEE Transactions on Computer--Aided Design of Integrated Circuits and Systems, Vol. CAD--3, No. 4, October 1984, pp. 257 -- 264.

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.

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

On Minimizing the Number of Page Faults with Complete Information, Proceedings of the 10th IMACS World Congress on Systems Simulation and Scientific Computation, Vol. IV, August 1982, pp. 279 -- 281.

Unit Execution Time Shop Problems, Mathematics of Operations Research, Vol. 7, No. 1, February 1982, pp. 57 -- 66.

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.

Preemptive Scheduling of Parallel Processors, ORSA/TIMS Joint National Meeting, Houston Texas, October 1981.

On the Complexity of Computing Bilinear Forms with (0,1) Constants, (with J. JaJa), Journal of Computer and Systems Sciences, Vol. 20, February 1980, pp. 77 -- 95.

Evaluating Arithmetic Expressions with Algebraic Identities is Hard, (with J. JaJa), Proceedings of the 1979 Conference on Information Science and Systems, March 1979, pp. 167 -- 173.

NP--hard Shop Problems, Technical Report CS--79--35, The Pennsylvania State University, May 1979, (proofs of theorems in ``Unit Execution Time Shop Problems'' appear in this paper).

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

Flowshop and Jobshop Schedules: Complexity and Approximation, (with S. Sahni), Operations Research, Vol. 26, No. 1, January--February 1978, pp. 36 -- 52.

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.

On Flowshop and Jobshop Schedules, (with S. Sahni), ORSA/TIMS Special Interest Conference on Scheduling, Orlando Florida, February 1976.

P--Complete Problems and Approximate Solutions, (with S. Sahni), Proceedings of the 15th Annual IEEE Symposium on Switching and Automata Theory, October 1974, pp. 28 -- 32.