43754145
Heaps with Bits
In this paper, we show how to improve the complexity of heap operations and heapsort using extra bits. We first study parallel complexity of implementing priority queue operations on a heap. While the insertion of a new element into a heap can be done as fast as parallel searching, we show how to delete the smallest element from a heap in constant time with a sublinear number of processors, and in sublogarithmic time with a sublogarithmic number of processors. The models of parallel computation used are the CREW PRAM and the CRCW PRAM. Our results improve those of previously known algorithms.
6192242
Computing Maximum-Scoring Segments in Almost Linear Time
Given a sequence, the problem studied in this paper is to find a set of k disjoint continuous subsequences such that the total sum of all elements in the set is maximized. This problem arises naturally in the analysis of DNA sequences. The previous best known algorithm requires Θ(n log n) time in the worst case. For a given sequence of length n, we present an almost linear-time algorithm for this problem. Our algorithm uses a disjoint-set data structure and requires O(nα(n, n)) time in the worst case, where α(n, n) is the inverse Ackermann function.
43053494
Heaps with Bits
We show how to improve the complexity of heap operations and heapsort using extra bits. We first study the parallel complexity of implementing priority queue operations on a heap. The tradeoff betw ...
1746401
On the Effective Enumerability of NP Problems
In the field of computational optimization, it is often the case that we are given an instance of an NP problem and asked to enumerate the first few best solutions to the instance. Motivated by this, we propose in this paper a new framework to measure the effective enumerability of NP optimization problems. More specifically, given an instance of an NP problem, we consider the parameterized problem of enumerating a given number of best solutions to the instance, and study its average complexity in terms of the number of solutions. Our framework is different from the previously-proposed ones. For example, although it is known that counting the number of k-paths in a graph is #W[1]-complete, we present a fixed-parameter enumeration algorithm for the problem. We show that most algorithmic techniques for fixed-parameter tractable problems, such as search trees, color coding, and bounded treewidth, can be used for parameterized enumerations. In addition, we design elegant and new enumeration techniques and show how to generate small-size structures and enumerate solutions efficiently.
40686134
Probabilistic analysis of connectivity on mesh networks
Mesh networks are among the most important network topologies in massive multiprocessor parallel systems. This paper proposes a new method for calculating the connectivity probability for mesh networks, which uses thorough mathematical methods to derive the relationship between the network node failure probability and the network connectivity probability in mesh networks. The results show that practical mesh networks can remain connected with very high probability. For example, it is formally proved that when the network node failure probability is bounded by 0.12%, the mesh networks with up to forty thousand nodes remain connected with probability larger than 99%. Our methods are also useful for deriving lower bounds on the connectivity probability for other computer networks.
1481165
Improved algorithms for path, matching, and packing problems
Improved randomized and deterministic algorithms are presented for PATH, MATCHING, and PACKING problems. Our randomized algorithms are based on the divide-and-conquer technique, and improve previous best algorithms for these problems. For example, for the <i>k</i>-PATH problem, our randomized algorithm runs in time <i>O</i>(4<sup><i>k</i></sup>k<sup>3.42</sup><i>m</i>) and space <i>O</i>(<i>nk</i>log<i>k</i> + <i>m</i>), improving the previous best randomized algorithm for the problem that runs in time <i>O</i>(5.44<sup><i>k</i></sup>km) and space <i>O</i>(2<sup><i>k</i></sup>kn + <i>m</i>). To achieve improved deterministic algorithms, we study a number of previously proposed de-randomization schemes, and also develop a new derandomization scheme. These studies result in a number of deterministic algorithms: one of time <i>O</i>(4<sup><i>k</i>+<i>o(k)</i></sup>m) for the <i>k</i>-PATH problem, one of time <i>O</i>(2.80<sup>3<i>k</i></sup>k nlog<sup>2</sup> <i>n</i>) for the 3-D MATCHING problem, and one of time <i>O</i>(4<sup>3<i>k</i>+<i>o(k)</i></sup>n) for the 3-SET PACKING problem. All these significantly improve previous best algorithms for the problems.
44387886
Fuzzy logic or Lukasiewicz logic: A clarification
Abstract We discuss some issues on fuzzy logic developed by Pavelka [Z. Math. Logic 25 (1979) 45–52, 119–134, 447–464] vs. the many-valued Lukasiewicz's logic. The focus is on the proper choice of fuzzy implication operations, a question which has been addressed many times in the fuzzy research literature. Pavelka had shown in 1979 that the only natural way of formalizing fuzzy logic for truth values in the unit interval [0, 1] is by using Lukasiewicz's implication operator a → b = min {1, 1 - a + b } or some isomorphic form of it. Many other papers around the same time had attempted to formulate alternative definitions for a → b by giving intuitive justifications. There continues to be some confusion, however, even today about the right notion of fuzzy logic. Much of this confusion lies in the use of improper “an” (“or”) and the “not” operations and a misunderstanding of some of the key differences between “proofs” or inferencing in fuzzy logic and those in Lukasiewicz's logic. We point out the need for defining the strong conjunction operator “⊗” in connection with fuzzy Modus-ponens rule and why we do not need the fuzzy Syllogism inference rule. We formulate two requirements of the fuzzy implication operator, which are satisfied by Lukasiewicz's a → b , but which fail for many of the alternative definitions for “→”.
7206524
Interactive construction of multi-segment curved handles
In this work, we present a method to interactively create multi-segment, curved handles between two star-shaped faces of an orientable 2-manifold mesh or to connect two 2-manifold meshes along such faces. The presented algorithm combines a very simple 2D morphing algorithm with Hermite interpolation to construct the handle. Based on the method, we have developed a user interface tool that allows users to simply and easily create multi-segment curved handles.