This page, and any PDF documents linked on this page, are no longer maintained and may not meet accessibility standards. To request an accessible version of any content, please contact us.
DIMACS Technical Reports Published in 1993
Obtaining Reports
Most technical reports are available on-line and we encourage
downloading. Reports that are not available
may be ordered by email to
tech@dimacs.rutgers.edu
Be sure to include the numbers of the reports needed and your full
Postal Address.
Problems with Technical Reports?
We try to check on the accessibility of technical reports regularly, but
mistakes do happen. If you have trouble obtaining reports, please send email to
tech@dimacs.rutgers.edu identifying the
report you had trouble with.
93-01
Abstract:
A Randomized Algorithm for Finding
Maximum with O((log n)^2) Polynomial Tests 93-02
Abstract:
Projective Orientations of
Matroids 93-03
Abstract:
k-Neighborhood
Covering and Independence Problems 93-04
Abstract:
A Polynomial-time
Algorithm for the Phylogeny Problem
When the Number of Character States is Fixed
93-05
Abstract:
Monotone Gray Codes and
the Middle Levels Problem 93-06
Abstract:
Optimal Compression
of Propositional Horn Knowledge Bases: Complexity and Approximation 93-07
Abstract:
On Computing Algebraic Functions Using Logarithms and Exponentials 93-08
Abstract:
Hilbert Series of Group Representations and Grobner Bases for Generic Modules 93-09
Abstract:
Asymptotic Results for Permutation Groups
(Abstract only; please order paper copy.)
Laszlo Pyber
93-10
Abstract:
Probabilistically
Checkable Debate Systems and Approximation Algorithms for
PSPACE-Hard Functions 93-11
Abstract:
The
L(2,1)-Labeling Problem on Graphs 93-12
Abstract:
A Tight Bound for Edge Guards in Rectilinear Monotone Polygons 93-13
Abstract:
Combinatorial Optimization and Computations in the Ring of Polynomials 93-14
Abstract:
Testing Simple Polygons 93-15
Abstract:
Enumerating Consecutive and Nested Partitions for Graphs 93-16
Abstract:
Confluently Persistent Deques via Data-Structural Bootstrapping 93-17
Abstract:
On the Structure of Co-Critical Graphs 93-18
Abstract:
Convex Relaxations of 0-1 Quadratic Programming 93-19
Abstract:
Indefinite Trust Region Subproblems and Nonsymmetric
Eigenvalue Perturbations 93-20
Abstract:
A First-Order Isomorphism Theorem 93-21
Abstract:
Dept Reduction for Noncommutative Arithmetic Circuits 93-22
Abstract:
A Robust Model for Finding Optimal Evolutionary Trees 93-23
Abstract:
Consecutive Cuts and Paths, and Bounds on k-Terminal Reliability 93-24
Abstract:
Weighted Independent Perfect Domination on Cocomparability Graphs 93-25
Abstract:
The Russian Option: Reduced Regret 93-26
Abstract:
A Dual Russian Option for Selling Short 93-27
Abstract:
Non-Stanley Bounds for Network Reliability 93-28
Abstract:
Some Open Problems on Reliability Polynomials 93-29
Abstract:
Combinatorial Optimization: A Survey 93-30
Abstract:
Lazy Structure Sharing for Query Optimization 93-31
Abstract:
Constructing Language Instances Based on Partial Information 93-32
Abstract:
Research Problems in Discrete Geometry:
Packing and Covering
(Abstract only; please order paper copy.)
William Moser and Janos Pach
93-33
Abstract:
Inverse Theorems in Additive Number Theory 93-34
Abstract:
Trust Regions and the
Quadratic Assignment Problem
(Abstract only, please order paper copy.)
Stefan E. Karisch, Franz Rendl, and Henry Wolkowicz
93-35
Abstract:
Entropy Splitting Hypergraphs 93-36
Abstract:
Workshop on Parallel Algorithms for Unstructured & Dynamic Problems 93-37
Abstract:
Quasi-Acyclic Propositional Horn Knowledge Bases: Optimal Compression 93-38
Abstract:
Parallel Processing of Discrete Optimization Problems 93-39
Abstract:
The Simplex Algorithm with a New Primal and Dual Pivot Rule 93-40
Abstract:
On Lattice-Free Polytopes 93-41
Abstract:
On Edge Bijections of Graphs 93-42
Abstract:
On a Covering Property of Maximal Sperner Families 93-43
Abstract:
Relationships Among PL, #L, and the Determinant 93-44
Abstract:
Half-integral Flows in a Planar Graph With Four Holes
(Abstract only; please order paper copy.)
Alexander V. Karzanov
93-45
Abstract:
An Efficient Algorithm for Dynamic Text Indexing
Ming Gu, Martin Farach and Richard Beigel
93-46
Abstract:
Fast Comparison of Evolutionary Trees
Martin Farach and Mikkel Thorup
93-47
Abstract:
A New Approach to the Construction of Optimal Designs
R.H. Hardin and N.J.A. Sloane
93-48
Abstract:
Covering Arrays and Intersecting Codes
N.J.A. Sloane
93-49
Abstract:
The Nordstrom-Robinson Code is the Binary Image of the Octacode
G. David Forney, Jr., N.J.A. Sloane and Mitchell D. Trott
93-50
Abstract:
A Linear Construction for Certain Kerdock and Preparata Codes
A.R. Calderbank, A.R. Hammons, Jr., and P. Vijay Kumar
93-51
Abstract:
Operating Manual for Gosset: A General-Purpose Program for
Constructing Experimental Designs (Second Edition)
R.H. Hardin and N.J.A. Sloane
93-52
Abstract:
The Z sub 4-Linearity of Kerdock, Preparata, Goethals and Related Codes
A.R. Hammons, Jr., P. Vijay Kumar, A.R. Calderbank, N.J.A. Sloane, and Patrick Sole
93-53
Abstract:
Quaternary Constructions for the Binary Single-Error-Correcting
Codes of Julin, Best and Others
J.H. Conway and N.J.A. Sloane
93-54
Abstract:
Expressing (a sup 2 + b sup 2 + c sup 2 + d sup 2) sup 3
as a Sum of 23 Sixth Powers
R.H. Hardin and N.J.A. Sloane
93-55
Abstract:
D sub 4, E sub 8, Leech and Certain Other Lattices are Symplectic
J.H. Conway and N.J.A. Sloane
93-56
Abstract:
A Pedestrian Approach to Ray Shooting: Shoot a Ray, Take a Walk
John Hershberger and Subhash Suri
93-57
Abstract:
Finding a Shortest Diagonal of a Simple Polygon in Linear Time
John Hershberger and Subhash Suri
93-58
Abstract:
Matrix Searching with the Shortest Path Metric
John Hershberger and Subhash Suri
93-59
Abstract:
Can Visibility Graphs Be Represented Compactly?
Pankaj K. Agarwal, Noga Alon, Boris Aronov, Subhash Suri
93-60
Abstract:
Shortcutting Planar Digraphs and
(second part of this paper in postscript) 93-61
Abstract:
Controlled Grammatic Ambiguity
First Part ,
Second Part , and
Third Part .
Mikkel Thorup
93-62
Abstract:
Minors and the Chromatic Index of r-graphs 93-63
Abstract:
A Note on a Conjecture of Toft
T. R. Jensen and F. B. Shepherd
93-64
Abstract:
On Enumeration of Near to Best Solutions in Discrete and Dynamic Programming
Joseph V. Romanovsky
93-65
Abstract:
Instance-Hiding Proof Systems
D. Beaver, J. Feigenbaum, R. Ostrovsky, and V. Shoup
93-66
Abstract:
The Least Possible Value at Zero of Some Nonnegative Cosine Polynomials
Szilard Gy. Revesz
93-67
Abstract:
Approximation Clustering for Homogeneous Data Tables
(Abstract only; please order paper copy.)
Boris Mirkin
93-68
Abstract:
Generalization of the Tetrad Representation Theorem
Glenn Shafer, Alexander Kogan and Peter Spirtes
93-69
Abstract:
Some Experimental and Theoretical Results on Test Case Generators
for the Maximum Clique Problem
Laura A. Sanchis and Arun Jagota
93-70
Abstract:
Eigenvalues and Expansion of Regular Graphs
Nabil Kahale
93-71
Abstract:
A Randomized Linear-Time Algorithm for Finding Minimum Spanning
Philip N. Klein and Robert E. Tarjan
93-72
Abstract:
Symmetric Quasi-Definite Matrices
Robert J. Vanderbei
93-73
Abstract:
Affine-Scaling Trajectories Associated with a Semi-Infinite Linear Program
Robert J. Vanderbei
93-74
Abstract:
Brownian Bandits
Avi Mandelbaum and Robert J. Vanderbei
93-75
Abstract:
Interior-Point Methods for Max-Min Eigenvalue Problems
Franz Rendl, Robert J. Vanderbei, and Henry Wolkowicz
93-76
Abstract:
Bipartite Dimensions and Bipartite Degrees of Graphs
Peter C. Fishburn and Peter L. Hammer
93-77
Abstract:
An Analog of Freiman's Theorem in Groups
Imre Z. Ruzsa
93-78
Abstract:
On Reducing the Cut Ratio to the Multicut Problem
Nabil Kahale
93-79
Abstract:
Random Debaters and the Hardness of Approximating Stochastic Functions
Anne Condon, Joan Feigenbaum, Carsten Lund and Peter Shor
93-80
Abstract:
On Sums With Small Prime Factors
(Abstract only; Please order paper copy.)
Gabor Sarkozy
93-81
Abstract:
Fast Parallel Algorithms or Finding Hamiltonian Cycles and Trees in Graphs
(Abstract only; Please order paper copy.)
Gabor Sarkozy
93-82
Abstract:
A Geometric Approach for Denoting and Intersecting TR Subgroups of the Euclidean Group
Yanxi Liu
93-83
Abstract:
Isoperimetric Inequalities and Eigenvalues
Nabil Kahale
93-84
Abstract:
Notes on the Kolakoski Sequence
Vasek Chvatal
93-85
Abstract:
On the Diameter of the Symmetric Traveling Salesman Polytope
(Abstract only; Please order paper copy.)
Fred J. Rispoli
93-87
Abstract:
Workshop on Models, Architectures, and
Technologies for Parallel Computation
(Abstract only. Please order paper copy.)
P.B. Gibbons, R.M. Karp, C.E. Leiserson, G.M. Papadopoulos
93-88
Abstract:
On Lattices Equivalent to Their Duals 93-89
Abstract:
Optimization Methods for Computing Global Minima of Nonconvex Potential Energy Functions 93-90
Abstract:
Workshop on Parallel Algorithms:
From Solving Combinatorial Problems to Solving Grand Challenge Problems
(Abstract only. Please order paper copy.)
James Flanagan, Yossi Matias, and Vijaya Ramachandran
93-91
Abstract:
Balancing Updates vs Queries for
the Partial Sum Problem
(Abstract only. Please order paper copy.)
Haripriyan Hampapuram and Michael L. Fredman
93-92
Abstract:
DIMACS Annual Report 93-93
Abstract:
On the Very Weak 0-1 Law for Random Graphs With Orders
tech@dimacs.rutgers.edu
Contacting the Center 
Return to Tech Reports Page
DIMACS Homepage