DIMACS Technical Reports Published in 1991

Obtaining Reports

Problems with Technical Reports?

• 91-1 Connectivity of Consecutive-d Digraphs (II) D.Z. Du, D.F. Hsu, G.W. Peck
• 91-2 Rudimentary Reductions Revisited Allender, Gore
• 91-3 Counting Circular Arc Intersection Agarwal, Sharir
• 91-4 Niche Numbers Fishburn, Gehrlein
• 91-5 The Cell Structures of Certain Lattices Conway, Sloane
• 91-6 On the Success Probability of the Two Provers in One-Round Proof Systems Feige
• 91-7 Scaling Matrices to Prescribed Row and Column Maxima Rothblum, H. Schneider, M.H. Schneider
• 91-8 Stable Marriages: Substituting Linearity for Discreteness Roth, Rothblum, VandeVate
• 91-9 A Discounted-Cost Continuous-Time Flexible Manufacturing and Operator Scheduling Model Solved by Deconvexification Over Time Eaves, Rothblum
• 91-10 Optimality of Monotone Assemblies for Coherent Systems Composed of Series Modules Hwang, Rothblum
• 91-11 Approximation of the Spectral Radius, Corresponding Eigenvector and Second Largest Modulus of an Eigenvalue for Square Nonnegative Irreducible Matrices Gross, Rothblum
• 91-12 Taylor Expansions of Eigenvalue of Perturbed Matrices with Applications to Spectral Radii of Nonnegative Matrices Haviv, Ritov, Rothblum
• 91-13 Dynamic Recomputation Can't Extend the Optimality-Range of Priority Indices Rothblum, Rothkopf
• 91-14 Recent Results on Some no-so-Recent Hypergraph Matching and Covering Problems Kahn
• 91-15 On the Role of Discrete Bid Levels in Oral Auctions Rothkopf, Harstad
• 91-16 Applications of a New Space Partitioning Technique Agarwal, Sharir
• 91-17 The Modulus of Polynomials with Zeros on the Unit Circle - A Problem of Erdos Beck
• 91-18 Workshop on Applications of Combinatorial Optimization in Science and Technology COST
• 91-19 Flat Polynomials on the Unit Circle-Note on a Problem of Littlewood Beck
• 91-20 Quasi-random 2 Coloring of Point Sets Beck
• 91-21 An Algorithmic Approach to the Lovasz Local Lemma. I. Beck
• 91-22 The Reversing Number of a Digraph Barthelemy, Hudry, Isaak, Roberts, Tesman
• 91-23 On Complexity of Subset Interconnection Designs Du
• 91-24 Fast Approximation Schemes for Convex Programs with Many Blocks and Coupling Constraints Grigoriadis, Khachiyan Scanned File
• 91-25 Generalization of the Komogorov-Smirnov Goodness-of Fit Test, Using Group Invariance Feltz, Goldin
• 91-26 Transitions in Geometric Minimum Spanning Trees Monma, Suri
• 91-27 Relations Between Spectral and Classification Properties of Multigraphs Bolla
• 91-28 Scalings of Matrices Satisfying Line-Product Constraints and Generalizations Rothblum, and Zenios
• 91-29 On a Triangulation of the 3-ball and the Solid Torus Bohus, Jockusch, Lee, and Prabhu
• 91-30 A New All-Pairs Shortest-Path Algorithm Catherine C. McGeoch
• 91-31 Cycles of Length 0 Modulo 4 in Graphs Dean, Lesniak, Saito
• 91-32 Cycles Modulo 3 Dean, Toft, Kaneko, Ota
• 91-33 Quo Vadis, Graph Theory? Roberts
• 91-34 On Heuristics for Steiner Minimum Trees Ding-Zhu Du
• 91-35 Improved Performance Guarantee of Randomized On-Line Graph Coloring Magnus M. Halldorsson
• 91-36 Workshop Summery: Structural Complexity and Cryptography Eric Allender, Jin-yi Cai, Joan Feigenbaum
• 91-37 Order Analogues and Betti Polynomials Lynne Butler
• 91-38 Note: On the Last New Vertex Visited by a Random Walk Lovasz, Winkler
• 91-39 A Digital Signature Scheme and a Public-Key Cryptosystems 1 based on Elliptic Curves over Z Ueli M. Maurer
• 91-40 Rounds in Communication Complexity Revisited Noam Nisan, Avi Wigderson
• 91-41 How to Compute the Volume Laszlo Lovasz
• 91-42 PSPACE is Provable by Two Provers in One Round Jin-Yi Cai, Anne Condon, Richard J. Lipton
• 91-43 Probabilistic Behavior of Shortest Paths Over Unbounded Regions Andrew Chi-Chih Yao
• 91-44 Most Reliable Double Loop Networks in Survival Reliability X.D. Hu, F.K. Hwang, Wen-Ch'ing Winnie Li
• 91-45 A Competitive Algorithm for the Counterfeit Coin Problem X.D. Hu, F.K. Hwang
• 91-46 Cutting Numbers for the Forward Loop Backward Hop Network X.D. Hu, F.K. Hwang
• 91-47 Generalization of an Engineering Principle F.K. Hwang, U.G. Rothblum
• 91-48 Renewal Proposal to National Scientific Foundation Science and Technology Centers
• 91-49 Search Problems in the Decision Tree Model Laszlo Lovasz, Moni Naor, Ilan Newman, Avi Wigderson
• 91-50 Program Checkers for Probability Generation Sampath Kannan, Andrew Yao
• 91-51 Combinatorial Geometry Janos Pach, Pankaj K. Agarwal
• 91-52 Interactive Proofs with Space Bounded Provers Ronitt Rubinfeld
• 91-53 Greedily Solvable Transportation Networks and Edge-Guided Vertex Elimination Ilan Adler, Ron Shami
• 91-54 Complexity and Algorithms for Reasoning about Time: A Graph-Theoretic Approach Martin C. Golumbic, Ron Shamir
• 91-55 Checking Weak Programs: The Case of Small Dimensional Linear Programming Hugo Krawczyk
• 91-56 Graph Entropy and Formula Complexity Jaikumar Radhakrishnan
• 91-57 On the Optimal Strongly Connected Orientations of City Street Graphs IV: Four East-West Avenues or North-South Streets Fred S. Roberts, Yonghua Xu
• 91-58 On the Indicator Function of the Plurality Function Fred S. Roberts
• 91-59 Limitations on Conclusions Using Scales of Measurement Fred S. Roberts
• 91-60 On the Composition of Zero-Knowledge Proof Systems Oded Goldreich, Hugo Krawczyk
• 91-61 Proof of the 4/3 Conjecture for Preemptive vs. Nonpreemptive Two-Processor Scheduling E.G. Coffman, M.R. Garey
• 91-62 3-Choosable Complete Bipartite Graphs N.V.R. Mahadev, Fred S. Roberts, Prakash Santhanakrishnan
• 91-63 Complexity Results for POMSET Languages Joan Feigenbaum, Jeremy A. Kahn, Carsten Lund
• 91-64 Difference Sets Without k-th Powers A. Balog, J. Pelikan, J. Pintz, E. Szemeredi
• 91-65 Singularity Probabilities for Random Plus or Minus 1 Matrices Jeff Kahn, Janos Komlos, Endre Szemeredi
• 91-66 On a Problem in Additive Number Theory A. Sarkozy, E. Szemeredi
• 91-67 Nonnegative Ranks, Decompositions and Factorizations of Nonnegative Matrices Joel E. Cohen, Uriel G. Rothblum, RUTCOR
• 91-68 Using A Characterization of Feasibility of Transportation n Problems to Establish the Pairwise Connectedness of R with Respect to Partial Orders Uriel G. Rothblum, RUTCOR
• 91-69 Monotone Optimal Multi-Partitions Using Schur Convexity with Respect to Partial Orders Frank K. Hwang, Uriel G. Rothblum, RUTCOR, Larry Shepp
• 91-70 Majorization and Schur Convexity with Respect to Partial Orders Frank K. Hwang, Uriel Rothblum, RUTCOR
• 91-71 Covering With Latin Transversals Noga Alon, Joel Spencer, Prasad Tetali
• 91-72 Three Thresholds for a Liar Joel Spencer, Peter Winkler
• 91-73 Approximate Solution of Matrix Games in Parallel M.D. Grigoriadis, L.G. Khachiyan
• 91-74 Proper and Unit Tolerance Graphs K.P. Bogart, G. Isaak, L. Langley, P.C. Fishburn
• 91-75 Almost-Everywhere Complexity Hierarchies for Nondeterministic Time Eric Allender, Richard Beigel, Ulrich Hertrampf, Steven Homer
• 91-76 Geometric Transversal Theory Jacob E. Goodman, Richard Pollack, Rephael Wenger
• 91-77 On the Running Time of the Adleman-Pomerance-Rumely Primality Test J. Pelikan, J. Pintz, Endre Szemeredi
• 91-78 Self-Testing/Correcting for Polynomials and the Approximate Functions Peter Gemmell, Richard Lipton, Ronitt Rubinfeld, Madhu Sudan, Avi Wigderson

Return to Tech Reports Page

DIMACS Homepage