Parallel Dixon Matrices by Bracket

It is known that the Dixon matrix can be constructed in parallel either by entry or by diagonal. This paper presents another parallel matrix construction, this time by bracket. The parallel by bracket algorithm is the fastest among the three, but not surprisingly it requires the highest number of processors. The method also shows analytically that the Dixon matrix has a total of m(m+1)²(m+2)n(n+1)²(n+2)/36 brackets but only mn(m+1)(n+1)(mn+2m+2n+1)/6 of them are distinct.     

Efficient algorithms for finding minimum spanning trees in undirected and directed graphs

Recently, Fredman and Tarjan invented a new, especially efficient form of heap (priority queue). Their data structure, theFibonacci heap (or F-heap) supports arbitrary deletion inO(logn) amortized time and other heap operations inO(1) amortized time. In this paper we use F-heaps to obtain fast algorithms for finding minimum spanning trees in undirected and directed graphs. For an undirected graph containingn vertices andm edges, our minimum spanning tree algorithm runs inO(m logβ (m, n)) time, improved fromO(mβ(m, n)) time, whereβ(m, n)=min {i|log⁽ⁱ⁾ n ≦m/n}. Our minimum spanning tree algorithm for directed graphs runs inO(n logn + m) time, improved fromO(n log n +m log log log_(m/n+2) n). Both algorithms can be extended to allow a degree constraint at one vertex. Research supported in part by National Science Foundation Grant MCS-8302648. Research supported in part by National Science Foundation Grant MCS-8303139. Research supported in part by National Science Foundation Grant MCS-8300984 and a United States Army Research Office Program Fellowship, DAAG29-83-GO020.     

Semi-Balanced Colorings of Graphs: Generalized 2-Colorings Based on a Relaxed Discrepancy Condition

We generalize the concept of a 2-coloring of a graph to what we call a semi-balanced coloring by relaxing a certain discrepancy condition on the shortest-paths hypergraph of the graph. Let G be an undirected, unweighted, connected graph with n vertices and m edges. We prove that the number of different semi-balanced colorings of G is: (1) at most n+1 if G is bipartite; (2) at most m if G is non-bipartite and triangle-free; and (3) at most m+1 if G is non-bipartite. Based on the above combinatorial investigation, we design an algorithm to enumerate all semi-balanced colorings of G in O(nm²) time.Acknowledgments The authors thank Tetsuo Asano, Naoki Katoh, Kunihiko Sadakane, and Hisao Tamaki for helpful discussions and comments.Supported in part by Sweden-Japan FoundationFinal version received: November 17, 2003     

Lower bounds for the cardinality of minimal blocking sets in projective spaces

In this paper new lower bounds for the cardinality of minimal m-blocking sets are determined. Let r₂(q) be the number such that q+r₂(q)+1 is the cardinality of the smallest non-trivial line-blocking set in a plane of order q. If B is a minimal m-blocking set in PG(n,q) that contains at most q^m+q^m−1+…+q+1+r₂(q)·(∑_i=2m−n′^m−1qⁱ) points for an integer n′ satisfying mn′2m, then the dimension of B is at most n′. If the dimension of B is n′, then the following holds. The cardinality of B equals q^m+q^m−1+…+q+1+r₂(q)(∑_i=2m−n′^m−1qⁱ). For n′=m the set B is an m-dimensional subspace and for n′=m+1 the set B is a cone with an (m−2)-dimensional vertex over a non-trivial line-blocking set of cardinality q+r₂(q)+1 in a plane skew to the vertex. This result is due to Heim (Mitt. Math. Semin. Giessen 226 (1996), 4–82). For n′>m+1 and q not a prime the number q is a square and for q16 the set B is a Baer cone. If q is odd and |B|<q^m+q^m−1+…+q+1+r₂(q)(q^m−1+q^m−2), it follows from this result that the subspace generated by B has dimension at most m+1. Furthermore we prove that in this case, if , then B is an m-dimensional subspace or a cone with an (m−2)-dimensional vertex over a non-trivial line-blocking set of cardinality q+r₂(q)+1 in a plane skew to the vertex. For q=p^3h, p7 and q not a square we show this assertion for |B|q^m+q^m−1+…+q+1+q^2/3·(q^m−1+…+1).     

The number of edges of many faces in a line segment arrangement

We show that the maximum number of edges boundingm faces in an arrangement ofn line segments in the plane isO(m ^2/3 n ^2/3+n(n)+nlogm). This improves a previous upper bound of Edelsbrunner et al. [5] and almost matches the best known lower bound which is (m ^2/3 n ^2/3+n(n)). In addition, we show that the number of edges bounding anym faces in an arrangement ofn line segments with a total oft intersecting pairs isO(m ^2/3 t ^1/3+n(t/n)+nmin{logm,logt/n}), almost matching the lower bound of (m ^2/3 t ^1/3+n(t/n)) demonstrated in this paper.Work on this paper by the first and fourth authors has been partially supported by Office of Naval Research Grant N00014-87-K-0129, by National Science Foundation Grants DCR-83-20085 and CCR-89-01484. Work by the first author has also been supported by an AT&T Bell Laboratories Ph.D. scholarship at New York University and by DIMACS (Center for Discrete Mathematics and Theoretical Computer Science), a National Science Foundation Science and Technology Center (NSF-STC88-09648). Work by the second author has been supported by NSF under Grants CCR-87-14565 and CCR-89-21421. Work by the fourth author has additionally been supported by grants from the U.S.-Israeli Binational Science Foundation, the NCRD (the Israeli National Council for Research and Development) and the Fund for Basic Research in Electronics, Computers and Communication, administered by the Israeli National Academy of Sciences.     

A new graph triconnectivity algorithm and its parallelization

We present a new algorithm for finding the triconnected components of an undirected graph. The algorithm is based on a method of searching graphs called open ear decomposition. A parallel implementation of the algorithm on a CRCW PRAM runs inO(log² n) parallel time usingO(n+m) processors, wheren is the number of vertices andm is the number of edges in the graph.A preliminary version of this paper was presented at the19th Annual ACM Symposium on Theory of Computing, New York, NY, May 1987.Supported by NSF Grant DCR 8514961.Supported by NSF Grant ECS 8404866 and the Semiconductor Research Corporation Grant 86-12-109.     

Upper bounds for configurations and polytopes inR d

We give a new upper bound onn ^d(d+1)n on the number of realizable order types of simple configurations ofn points inR ^d , and ofn2d ² n on the number of realizable combinatorial types of simple configurations. It follows as a corollary of the first result that there are no more thann ^d(d+1)n combinatorially distinct labeled simplicial polytopes inR ^d withn vertices, which improves the best previous upper bound ofn ^{cn d/2}.Supported in part by NSF Grant DMS-8501492 and PSC-CUNY Grant 665258.Supported in part by NSF Grant DMS-8501947.     

Bounds for arrays of dots with distinct slopes or lengths

Ann×m sonar sequence is a subset of then×m grid with exactly one point in each column, such that the vectors determined by them are all distinct. We show that for fixedn the maximalm for which a sonar sequence exists satisfiesn–Cn ^11/20<m<n+4n ^2/3 for alln andm>n+c logn log logn for infinitely manyn.Another problem concerns the maximal numberD of points that can be selected from then×m grid so that all the vectors have slopes. We proven ^1/2Dn ^4/5 Supported by Hungarian National Foundation for Scientific Research, Grant No. 1901Research conducted by Herbert Taylor was sponsored in part by the Office of Naval Research under ONR Contract No. N00014-90-J-1341.     

Halfspace range search: An algorithmic application ofk-sets

Given a fixed setS ofn points inE ³ and a query plane, the halfspace range search problem asks for the retrieval of all points ofS on a chosen side of. We prove that withO(n(logn)⁸ (loglogn)⁴) storage it is possible to solve this problem inO(k+logn) time, wherek is the number of points to be reported. This result rests crucially on a new combinatorial derivation. We show that the total number ofj-sets (j=1, ...,k) realized by a set ofn points inE ³ isO(nk ⁵); ak-set is any subset ofS of sizek which can be separated from the rest ofS by a plane.Supported in part by NSF grants MCS 83-03925 and the Office of Naval Research and the Defense Advanced Research Projects Agency under contract N00014-83-K-0146 and ARPA Order No. 4786.Supported in part by Joint Services Electronics Program under Contract N00014-79-C-0424.     

Polynomial dual network simplex algorithms

We show how to use polynomial and strongly polynomial capacity scaling algorithms for the transshipment problem to design a polynomial dual network simplex pivot rule. Our best pivoting strategy leads to an O(m ² logn) bound on the number of pivots, wheren andm denotes the number of nodes and arcs in the input network. If the demands are integral and at mostB, we also give an O(m(m+n logn) min(lognB, m logn))-time implementation of a strategy that requires somewhat more pivots.Research supported by AFOSR-88-0088 through the Air Force Office of Scientific Research, by NSF grant DOM-8921835 and by grants from Prime Computer Corporation and UPS.Research supported by NSF Research Initiation Award CCR-900-8226, by U.S. Army Research Office Grant DAAL-03-91-G-0102, and by ONR Contract N00014-88-K-0166.Research supported in part by a Packard Fellowship, an NSF PYI award, a Sloan Fellowship, and by the National Science Foundation, the Air Force Office of Scientific Research, and the Office of Naval Research, through NSF grant DMS-8920550.     

Constant mean curvature hypersurfaces with two principal curvatures in a sphere

In this paper we consider a compact oriented hypersurface M ⁿ with constant mean curvature H and two distinct principal curvatures λ and μ with multiplicities (n − m) and m, respectively, immersed in the unit sphere S ⁿ⁺¹. Denote by f_ij{\phi_{ij}} the trace free part of the second fundamental form of M ⁿ , and Φ be the square of the length of f_ij{\phi_{ij}} . We obtain two integral formulas by using Φ and the polynomial P_H,m(x)=x²+ \fracn(n-2m)?{nm(n-m)}H x -n(1+H²){P_{H,m}(x)=x^{2}+ \frac{n(n-2m)}{\sqrt{nm(n-m)}}H x -n(1+H^{2})} . Assume that B _H,m is the square of the positive root of P _H,m (x) = 0. We show that if M ⁿ is a compact oriented hypersurface immersed in the sphere S ⁿ⁺¹ with constant mean curvatures H having two distinct principal curvatures λ and μ then either F = B_H,m{\Phi=B_{H,m}} or F = B_H,n-m{\Phi=B_{H,n-m}} . In particular, M ⁿ is the hypersurface S^n-m(r)×S^m(?{1-r²}){S^{n-m}(r)\times S^{m}(\sqrt{1-r^{2}})} .     

A parallel method for fast and practical high-order newton interpolation

We present parallel algorithms for the computation and evaluation of interpolating polynomials. The algorithms use parallel prefix techniques for the calculation of divided differences in the Newton representation of the interpolating polynomial. Forn+1 given input pairs, the proposed interpolation algorithm requires only 2 [log(n+1)]+2 parallel arithmetic steps and circuit sizeO(n ²), reducing the best known circuit size for parallel interpolation by a factor of logn. The algorithm for the computation of the divided differences is shown to be numerically stable and does not require equidistant points, precomputation, or the fast Fourier transform. We report on numerical experiments comparing this with other serial and parallel algorithms. The experiments indicate that the method can be very useful for very high-order interpolation, which is made possible for special sets of interpolation nodes.Supported in part by the National Science Foundation under Grant No. NSF DCR-8603722.Supported by the National Science Foundation under Grants No. US NSF MIP-8410110, US NSF DCR85-09970, and US NSF CCR-8717942 and AT&T under Grant AT&T AFFL67Sameh.     

Negative Latin square type partial difference sets and amorphic association schemes with Galois rings

A partial difference set (PDS) having parameters (n², r(n?1), n+r²?3r, r²?r) is called a Latin square type PDS, while a PDS having parameters (n², r(n+1), ?n+r²+3r, r² +r) is called a negative Latin square type PDS. There are relatively few known constructions of negative Latin square type PDSs, and nearly all of these are in elementary abelian groups. We show that there are three different groups of order 256 that have all possible negative Latin square type parameters. We then give generalized constructions of negative Latin square type PDSs in 2‐groups. We conclude by discussing how these results fit into the context of amorphic association schemes and by stating some open problems. © 2009 Wiley Periodicals, Inc. J Combin Designs 17: 266‐282, 2009     

Reduced Vertex Set Result for Interval Semidefinite Optimization Problems

In this paper we propose a reduced vertex result for the robust solution of uncertain semidefinite optimization problems subject to interval uncertainty. If the number of decision variables is m and the size of the coefficient matrices in the linear matrix inequality constraints is n×n, a direct vertex approach would require satisfaction of 2 ^{n(m+1)(n+1)/2} vertex constraints: a huge number, even for small values of n and m. The conditions derived here are instead based on the introduction of m slack variables and a subset of vertex coefficient matrices of cardinality 2 ⁿ⁻¹, thus reducing the problem to a practically manageable size, at least for small n. A similar size reduction is also obtained for a class of problems with affinely dependent interval uncertainty. This work is supported by MIUR under the FIRB project “Learning, Randomization and Guaranteed Predictive Inference for Complex Uncertain Systems,” and by CNR RSTL funds.     

Stable in situ sorting and minimum data movement

In this paper, we describe an algorithm to stably sort an array ofn elements using only a linear number of data movements and constant extra space, albeit in quadratic time. It was not known previously whether such an algorithm existed. When the input contains only a constant number of distinct values, we present a sequence ofin situ stable sorting algorithms makingO(n lg^(k+1) n+kn) comparisons (lg^(K) means lg iteratedk times and lg* the number of times the logarithm must be taken to give a result 0) andO(kn) data movements for any fixed valuek, culminating in one that makesO(n lg*n) comparisons and data movements. Stable versions of quicksort follow from these algorithms.Research supported by Natural Sciences and Engineering Research Council of Canada grant No.A-8237 and the Information Technology Research Centre of Ontario.Supported in part by a Research Initiation Grant from the Virginia Engineering Foundation.     

The number of nearest and farthest points to a compactum in Euclidean space

A typical (in the sense of Baire category) compactA inE, whereE is either the Euclidean spaceE ⁸,s≧2, or the separable Hilbert space ℍ, generates a dense subsetC ^n,m(A) of the underlying space, such that everyx∈C ^n,m(A) has exactlyn nearest andm farthest points fromA, whenevern andm are positive integers satisfyingn+m≦ dimE+2. Research of this author is in part supported by Consiglio Nazionale delle Ricerche, G.N.A.F.A., Italy.     

On the Growth of Positive Definite Double Sequences Which Are not Moment Sequences

For every a > 1, there is a function f : N²₀ → R, which is positive semidefinite but not a moment sequence, such that |f(m, n)| ≥ m+ n^a(m+n) for all (m, n). The constant 1 is the best possible.     

Random weightingT-statistics in linear regression models

In this paper, we have constructed a random weighting statistic to approximate the distribution of studentized least square estimator in a linear regression model with ideal accuracyo(n ^–1/2). Thus, we have provided a more practical distribution approximating method.Supported by the Doctoral Program Foundation of the Institute of Higher Education and the National Natural Science Foundation of China.     

Euclidean minimum spanning trees and bichromatic closest pairs

We present an algorithm to compute a Euclidean minimum spanning tree of a given setS ofN points inE ^d in timeO(F _d (N,N) log ^d N), whereF _d (n,m) is the time required to compute a bichromatic closest pair amongn red andm green points inE ^d . IfF _d (N,N)=Ω(N ^1+ε), for some fixed ɛ>0, then the running time improves toO(F _d (N,N)). Furthermore, we describe a randomized algorithm to compute a bichromatic closest pair in expected timeO((nm logn logm)^2/3+m log² n+n log² m) inE ₃, which yields anO(N ^4/3 log^4/3 N) expected time, algorithm for computing a Euclidean minimum spanning tree ofN points inE ³. Ind≥4 dimensions we obtain expected timeO((nm)^{1−1/([d/2]+1)+ε}+m logn+n logm) for the bichromatic closest pair problem andO(N ^{2−2/([d/2]+1)ε}) for the Euclidean minimum spanning tree problem, for any positive ɛ. The first, second, and fourth authors acknowledge support from the Center for Discrete Mathematics and Theoretical Computer Science (DIMACS), a National Science Foundation Science and Technology Center under NSF Grant STC 88-09648. The second author's work was supported by the National Science Foundation under Grant CCR-8714565. The third author's work was supported by the Deutsche Forschungsgemeinschaft under Grant A1 253/1-3, Schwerpunktprogramm “Datenstrukturen und effiziente Algorithmen”. The last two authors' work was also partially supported by the ESPRIT II Basic Research Action of the EC under Contract No. 3075 (project ALCOM).     

On a Class of Symmetric Balanced Generalized Weighing Matrices

Let q be a prime power and m a positive integer. A construction method is given to multiply the parametrs of an -circulant BGW(v=1+q+q ₂+·+q ^m , q ^m , q ^m –q ^m–1) over the cyclic group C _n of order n with (q–1)/n being an even integer, by the parameters of a symmetric BGW(1+q ^m+1, q ^m+1, q ^m+1–q ^m ) with zero diagonal over a cyclic group C _vn to generate a symmetric BGW(1+q+·+q ^2m+1,q ^2m+1,q ^2m+1–q ^2m) with zero diagonal, over the cyclic group C _n . Applications include two new infinite classes of strongly regular graphs with parametersSRG(36(1+25+·+25^2m+1),15(25)^2m+1,6(25)^2m+1,6(25)^2m+1), and SRG(36(1+49+·+49^2m+1),21(49)^2m+1,12(49)^2m+1,12(49)^2m+1).