The Infona portal uses cookies, i.e. strings of text saved by a browser on the user's device. The portal can access those files and use them to remember the user's data, such as their chosen settings (screen view, interface language, etc.), or their login data. By using the Infona portal the user accepts automatic saving and using this information for portal operation purposes. More information on the subject can be found in the Privacy Policy and Terms of Service. By closing this window the user confirms that they have read the information on cookie usage, and they accept the privacy policy and the way cookies are used by the portal. You can change the cookie settings in your browser.
Many of the interesting problems in Computer Science related to Software Engineering have yielded only to partial solutions or not at all. In the related areas of research denoted Communications Software Engineering and Protocols, most corresponding problems are on their way to a solution. In this presentation, we will explore some similarities and differences between these research areas by giving...
Mass production, as an idea, has had a long and successful history. First recognized and distilled in the early 19th century by such men as Adam Smith and Charles Babbage, it has since been successfully applied to virtually every manufacturing process, from farming to automobile manufacture
In this paper, we propose an O(mn2) time algorithm that finds all-pairs quickest paths in a given network N, where n and m are the numbers of nodes and arcs, respectively, in N. Besides, the quickest path between any two nodes can be determined in O(log m) time, provided O(mn2) time preprocessing is made.
We present a general constructive principle for the design of adaptive sorting algorithms that enables us to focus attention on the combinatorial properties of measures of presortedness rather than on the combinatorial properties of sorting algorithms. Using it, we obtain a practical adaptive sorting algorithm, optimal with respect to five important measures of presortedness and smoothly adaptive...
In this paper we study the complexity of rational functions and multirational functions. These include 1) functions containing the absolute value, max and min functions, 2) data structure functions such as sort, insert and merge 3) integer functions such as the gcd (greater common divisor), modulo, bitwise ‘and’ and 4) polynomial functions such as the gcd and modulo of two polynomials. We prove...
We present approximation algorithms for the Bandwidth Minimization Problem (BMP) for cases of special trees. The BMP has many different applications and has been studied for both graphs and matrices. The problem has important applications in large distributed processing systems and databases as well as communication theory. The technique presented here is used to provide a communication protocol for...
A new structure for representing binary images, called the Interpolation-Based Bintree is introduced. This structure combines the features of some existing representations such as linear quadtrees, binary trees, and interpolation-based codes, to improve the performance of operations manipulating graphics images. The implementation of this method is performed on both randomly generated and actual images...
The problem of coloring a set of n intervals (from the real line) with a set of k colors is studied. In such a coloring, two intervals may have the same color if and only if those intervals do not overlap. Two versions of the problem are considered. For the first, we provide an O(k+n) time algorithm for k-coloring a maximum cardinality subset of the intervals. The best previous algorithm for this...
We describe a linear-time algorithm that folds a triangulated simple polygon into a single triangle. Using this technique, we derive a particularly simple proof of Chvàtal's art gallery theorem and improve or simplify a number of algorithms that deal with triangulated simple polygons. We describe two improved algorithms, both based on the degree sequence of the boundary vertices of the given triangulated...
We establish the following relationship between the move-to-front heuristic for lists and the move-to-root heuristic for trees. Suppose we have a list s and we access an element x using the move-to-front heuristic to obtain a list s′. If we insert s into an empty binary search tree to obtain T and insert s′ into an empty binary search tree to obtain T′, then we can obtain T′ from T by accessing x...
We show that the internal path length of a red-black tree of size N is bounded above by 2N(log N−log log N)+O(N) and that this is, asymptotically, tight. This result further affirms a conjecture that whenever trees of size N, in a class of height-balanced binary trees, have height bounded from above by αlog2N, then the internal path length is bounded from above by α(log2N−log...
We characterize a family of AVL trees that have the maximum numbers of unbalanced nodes, nodes whose subtrees differ in height by one, for their heights and weights.
The complexity of the problem of selecting the k-th element of a sorted matrix is known. In this note we show a lower bound for such a problem in sorted X+Y. This lower bound is tight since the upper bound for sorted matrices holds for sorted X+Y.
Let S be a set of n points uniformly distributed in a unit square. We show that the expected value of the ratio between the length of the greedy triangulation of S and the minimum weight triangulation of S is constantly bounded. Our main result is an algorithm for constructing the greedy triangulation of S which runs in linear expected-time.
We consider the algorithmic complexity of generating labeled (directed and undirected) graphs under various distributions. We describe three natural optimality criteria for graph generating algorithms, and show algorithms that are optimal for many distributions.
We present a new scheme for storing shortest path information for a polyhedron. This scheme is obtained with a new observation on the properties of shortest path information of a polyhedron. Our scheme separates in a clear sense the problem of finding shortest paths and the problem of storing the shortest path information for retrieval. A tradeoff between time complexity O(d log n/log d) and space...
In a relational database model, checking the contraints of join dependency involves examining a set of n tuples and solving m1 constraint equalities. We derive a scheme called the (n,m)-JD in which the number of constraint equalities is reduced to m2, by forming cyclic combinations of the (disjoint) elements of the partition and increasing the number of intersection operations...
Set the date range to filter the displayed results. You can set a starting date, ending date or both. You can enter the dates manually or choose them from the calendar.