Rigidity of a simple extended lower triangular matrix

For the all-ones lower triangular matrices, the upper and lower bounds on rigidity are known to match [P. Pudlak, Z. Vavrin, Computation of rigidity of order n²/r for one simple matrix, Comment Math. Univ. Carolin. 32 (2) (1991) 213-218]. In this short note, we apply these techniques to the all-ones extended lower triangular matrices, to obtain upper and lower bounds with a small gap between the two; we show that the rigidity is .     

On small cuts separating an abelian Cayley graph into two equal parts

Let Γ be a connected directed Cayley graph with outdegreer. We show that there is a cutset of size ≤ (4n In(n/2))/D whose deletion creates a sinkB and a sourceB such that |B| = |B|. In particular Γ can be separated into two equal parts by deleting less than (8e/r)n ^(1-1/r) In(n/2) vertices. Our results improve a recent one proved by Annexstein and Baumslag [1]. As a main tool, we use inequalities from additive number theory.     

Transforming pseudo-triangulations

We study the problem of transforming pseudo-triangulations in the plane. We show that a pseudo-triangulation with n vertices can be transformed into another one using O(nlogn) flips only. This improves the previous bound O(n²) of Brönnimann et al. [Fall Workshop on Comput. Geometry, 2001]. We present an algorithm for computing a transformation between two pseudo-triangulations in O((f+n)logn) time where f is the number of flips.     

Evaluation and comparison of two efficient probabilistic primality testing algorithms

We analyse two recent probabilistic primality testing algorithms; the first one is derived from Miller [6] in a formulation given by Rabin [7], and the second one is from Solovay and Strassen [9]. Both decide whether or not an odd number n is prime in time O(m, lognM(n)) with an error probability less than α^m, for some $\text{0≤a<}\text{1}\text{2}$. Our comparison shows that the first algorithm is always more efficient than the second, both in probabilistic and algorithmic terms.     

Quadrilateral and tetrahedral mesh stripification using 2-factor partitioning of the dual graph

In order to find a 2-factor of a graph, there exists a O(n ^1.5) deterministic algorithm [7] and a O(n ³) randomized algorithm [14]. In this paper, we propose novel O(nlog³ nloglogn) algorithms to find a 2-factor, if one exists, of a graph in which all n vertices have degree 4 or less. Such graphs are actually dual graphs of quadrilateral and tetrahedral meshes. A 2-factor of such graphs implicitly defines a linear ordering of the mesh primitives in the form of strips. Further, by introducing a few additional primitives, we reduce the number of tetrahedral strips to represent the entire tetrahedral mesh and represent the entire quad surface using a single quad strip.     

Monotone Boolean dualization is in co-NP[logn]

In 1996, Fredman and Khachiyan [J. Algorithms 21 (1996) 618-628] presented a remarkable algorithm for the problem of checking the duality of a pair of monotone Boolean expressions in disjunctive normal form. Their algorithm runs in n^o(logn) time, thus giving evidence that the problem lies in an intermediate class between P and co-NP. In this paper we show that a modified version of their algorithm requires deterministic polynomial time plus O(log²n) nondeterministic guesses, thus placing the problem in the class co-NP[log²n]. Our nondeterministic version has also the advantage of having a simpler analysis than the deterministic one.     

Note on covering monotone orthogonal polygons with star-shaped polygons

In 1986, Keil provided an O(n²) time algorithm for the problem of covering monotone orthogonal polygons with the minimum number of r-star-shaped orthogonal polygons. This was later improved to O(n) time and space by Gewali et al. in [L. Gewali, M. Keil, S.C. Ntafos, On covering orthogonal polygons with star-shaped polygons, Information Sciences 65 (1992) 45-63]. In this paper we simplify the latter algorithm—we show that with a little modification, the first step Sweep1 of the discussed algorithm—which computes the top ceilings of horizontal grid segments—can be omitted.In addition, for the minimum orthogonal guard problem in the considered class of polygons, our approach provides a linear time algorithm which uses O(k) additional space, where k is the size of the optimal solution—the algorithm in [L. Gewali, M. Keil, S.C. Ntafos, On covering orthogonal polygons with star-shaped polygons, Information Sciences 65 (1992) 45-63] uses both O(n) time and O(n) additional space.     

How much precision is needed to compare two sums of square roots of integers?

In this paper, we investigate the problem of the minimum nonzero difference between two sums of square roots of integers. Let r(n,k) be the minimum positive value of where ai and bi are integers not larger than integer n. We prove by an explicit construction that r(n,k)=O(n−2k+3/2) for fixed k and any n. Our result implies that in order to compare two sums of k square roots of integers with at most d digits per integer, one might need precision of as many as digits. We also prove that this bound is optimal for a wide range of integers, i.e., r(n,k)=Θ(n−2k+3/2) for fixed k and for those integers in the form of and , where n^′ is any integer satisfied the form and i is any integer in [0,k−1]. We finally show that for k=2 and any n, this bound is also optimal, i.e., r(n,2)=Θ(n−7/2).     

Multisearch Techniques: Parallel Data Structures on Mesh-Connected Computers

The multisearch problem is defined as follows. Given a data structure D modeled as a graph with n constant-degree nodes, perform O(n) searches on D. Let r be the length of the longest search path associated with a search process, and assume that the paths are determined "on-line." That is, the search paths may overlap arbitrarily. In this paper, we solve the multisearch problem for certain classes of graphs in O([formula] + r ([formula]/log n)) time on a [formula] × [formula]n mesh-connected computer. For many data structures, the search path traversed when answering one search query has length r = O(log n). For these cases, our algorithm processes O(n) such queries in asymptotically optimal Θ([formula]) time. The classes of graphs we consider contain many of the important data structures that arise in practice, ranging from simple trees to Kirkpatrick hierarchical search DAGs. Multisearch is a useful abstraction that can be used to implement parallel versions of standard sequential data structures on a mesh. As example applications, we consider a variety of parallel on-line tree traversals, as well as hierarchical representations of polyhedra and its myriad of applications (line-polyhedron intersection queries, multiple tangent plane determination, intersecting convex polyhedra, and three-dimensional convex hull).     

Number of quantifiers is better than number of tape cells

We introduce a new complexity measure, QN[f(n)], which measures the size of sentences from predicate calculus needed to express a given property. We show that: NSPACE[f(n)]?QN[(f(n))²/log n]?DSPACE[(f(n))²]. Fraisse-Ehrenfeucht games are used to prove sharp lower bounds in the measure.     

Translation sets of permutations: Enumeration of selfcomplementary step-cycles

For given integern>2, there corresponds to each step-cycle a set of permutations, called a translation set. All the translation sets of permutations on the setS={1, 2, ...,n?1} form a set of equivalence classes on the set of all permutations onS. The selfcomplementary step-cycles are described and enumerated. A more general introduction to translation sets may be found in [4] and [3].     

Online rectangle filling

We study an online geometric problem arising in channel-aware scheduling of wireless networks, which we call the online rectangle filling. We present an online algorithm (with one-lookahead) for this problem with a competitive ratio of 1.848, improving the previously best-known 8/3-competitive algorithm in Arora et al. (2006) [4]. We also prove a lower bound of 1.6358 on the competitive ratio of the problem, improving the previous 1.6 lower bound in [4]. In addition, we give an O(n²)-time optimal algorithm for the offline version of the problem, where n is the size of the input, which improves the O(n³)-time solution in Arora and Choi (2006) [3], Arora et al. (2006) [5]. Our techniques are based on interesting techniques and new observations of the combinatorial structures in the problem.     

Characterizing r-perfect codes in direct products of two and three cycles

An r-perfect code of a graph G=(V,E) is a set C⊆V such that the r-balls centered at vertices of C form a partition of V. It is proved that the direct product of Cm and Cn (r?1, m,n?2r+1) contains an r-perfect code if and only if m and n are each a multiple of ²(r+1)+r² and that the direct product of Cm, Cn, and C? (r?1, m,n,??2r+1) contains an r-perfect code if and only if m, n, and ? are each a multiple of r³+³(r+1). The corresponding r-codes are essentially unique. Also, r-perfect codes in C2r×Cn (r?2, n?2r) are characterized.     

Highly-fair bakery algorithm using symmetric tokens

This note proposes a new version of the bakery algorithm that: (i) assures fair tie-breaking when two or more processes choose same token number; and (ii) bounds the token numbers within the range [−n,n]. The algorithm is simple and uses one additional shared bit.     

An orthogonal systolic array for the algebraic path problem

This paper is devoted to the design of an orthogonal systolic array ofn(n+1) elementary processors which can solve any instance of the Algebraic Path Problem within only 5n?2 time steps, and is compared with the 7n?2 time steps of the hexagonal systolic array of Rote [8].     

Embedding Hypercubes and Related Networks into Mesh-Connected Processor Arrays

In this paper we study the problem of how computations programmed for hypercubes, and their bounded-degree relatives, the shuffle-exchange and cube-connected-cycles, can be efficiently emulated by mesh-connected arrays of processing elements. The emulations we present are implemented via graph embeddings. The graph embeddings we present are all optimal with respect to congestion, and are also noteworthy for they yield efficient emulation programs that are written in a SIMD style without the use of indirect addressing. The paper includes the three following emulation results, where each emulation algorithm requires no indirection. For any n ≥ 1 and fixed r ≥ 1, an n-sided r-dimensional mesh can emulate an n2ⁿ-node cube-connected-cycles network with slowdown Θ(2ⁿ/n^r−1), a 2ⁿ-node shuffle-exchange network with slowdown Θ(2ⁿ/n^r), and a 2ⁿ-node hypercube network operating in a weak model, with slowdown Θ(2ⁿ log n/n^r).     

On a simple randomized algorithm for finding a 2-factor in sparse graphs

We analyze the performance of a simple randomized algorithm for finding 2-factors in directed Hamiltonian graphs of out-degree at most two and in undirected Hamiltonian graphs of degree at most three. For the directed case, the algorithm finds a 2-factor in O(n²) expected time. The analysis of our algorithm is based on random walks on the line and interestingly resembles the analysis of a randomized algorithm for the 2-SAT problem given by Papadimitriou [On selecting a satisfying truth assignment, in: Proc. 32nd Annual IEEE Symp. on the Foundations of Computer Science (FOCS), 1991, p. 163]. For the undirected case, the algorithm finds a 2-factor in O(n³) expected time. We also analyze random versions of these graphs and show that cycles of length Ω(n/logn) can be found with high probability in polynomial time. This partially answers an open question of Broder et al. [Finding hidden Hamilton cycles, Random Structures Algorithms 5 (1994) 395] on finding hidden Hamiltonian cycles in sparse random graphs and improves on a result of Karger et al. [On approximating the longest path in a graph, Algorithmica 18 (1997) 82].     

Self-checking circuits and decoding algorithms for binary hamming and BCH codes and Reed-Solomon codes over GF(2 m )

We consider problems of detecting errors in combinational circuits and algorithms for the decoding of linear codes. We show that a totally self-checking combinatorial circuit for the decoding of a binary Hamming [n, k] code can be constructed if and only if n = 2 ^r ? 1, r = n?k. We introduce the notion of a totally self-checking combinational circuit detecting error clusters of size at most µ; for shortened Hamming [n,k] codes, we construct totally self-checking decoding combinational circuits detecting error clusters of size at most µ, 2 ≤ µ < n?k. We describe single-error protected and self-checking algorithms: the extended Euclidean algorithm and decoding algorithms for binary BCH codes and Reed-Solomon codes over GF(2 ^m ).     

A lower bound for the pigeonhole principle in tree-like Resolution by asymmetric Prover-Delayer games

In this note we show that the asymmetric Prover-Delayer game developed in Beyersdorff et al. (2010) [2] for Parameterized Resolution is also applicable to other tree-like proof systems. In particular, we use this asymmetric Prover-Delayer game to show a lower bound of the form ²Ω(nlogn) for the pigeonhole principle in tree-like Resolution. This gives a new and simpler proof of the same lower bound established by Iwama and Miyazaki (1999) [7] and Dantchev and Riis (2001) [5].     

A discrete geometry approach for dominant point detection

We propose two fast methods for dominant point detection and polygonal representation of noisy and possibly disconnected curves based on a study of the decomposition of the curve into the sequence of maximal blurred segments [2]. Starting from results of discrete geometry [3] and [4], the notion of maximal blurred segment of width ν[2] has been proposed, well adapted to possibly noisy curves. The first method uses a fixed parameter that is the width of considered maximal blurred segments. The second method is deduced from the first one based on a multi-width approach to obtain a non-parametric method that uses no threshold for working with noisy curves. Comparisons with other methods in the literature prove the efficiency of our approach. Thanks to a recent result [5] concerning the construction of the sequence of maximal blurred segments, the complexity of the proposed methods is O(n log n). An application of vectorization is also given in this paper.