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.
We study the complexity of finding the values and optimal strategies of mean payoff games, a family of perfect information games introduced by Ehrenfeucht and Mycielski. We describe a pseudopolynomial time algorithm for the solution of such games, the decision problem for which is in NP ∩ co-NP. Finally, we describe a polynomial reduction from mean payoff games to the simple stochastic games studied...
It is said that a set L1 in a class C1approximates a set L2 in a class C2 if L1 is a subset of L2. Approximation L1 is said to be optimal if there is no approximation L′1 such that L′1 ⊃ L1 and L′1 - L1 is infinite. When C1=P and C2=NP, it is known that there is no optimal...
In this paper, we introduce and show how to draw a practical graph structure known as clustered graphs. We present an algorithm which produces planar, straight-line, convex drawings of clustered graphs in O(n2.5) time. We also demonstrate an area lower bound and an angle upper bound for straight-line convex drawings of C-planar graphs. We show that such drawings require Ω(2n) area and the smallest...
In this paper we present a new algorithm that constructs an orthogonal drawing of a graph G with degree at most three. Even if we do not require any limitations neither to planar nor to biconnected graphs, we reach the best known results in the literarture: each edge has at most 1 bend, the total number of bends is ≤ n/2+1, and the area is ≤(n/2−1)2.
We propose and study a new constrained independence system. We obtain a sequence of results, including a matching theorem for bases of the system and introducing a set of light elements which give a lower bound for the objective function of a minimization problem in the system. We then demonstrate that the set of triangulations of a planar point set can be modeled as constrained independence systems...
In this paper, we study the complexity of 3D weak visibility. We obtain an O(n8) time and Θ(n6) space algorithm to compute the weakly visible region of a triangle F from another triangle G among general scenes, which are a set of n disjoint triangles. We also consider the cases when the scenes are rectilinear objects and polyhedral terrains. We show that in these special situations...
In NC, one can decompose an n-vertex rectilinear polygon into O(n) rectangles, allowing Steiner points, so that any horizontal or vertical segment inside the polygon intersects O(logn) rectangles.
We present a new data structure, the Leafary tree, for designing an efficient randomized algorithm for the Closest Pair Problem. Using this data structure, we show that the Closest Pair of n points in D-dimensional space, where, D≥2, is a fixed constant, can be found in O(n log n/log log n) expected time. The algorithm does not employ hashing.
We study the complexity of testing containment for a class of object-oriented conjunctive queries. We show that the containment problem is ∏ 2p -hard. Together with a previous result, the containment problem is complete in ∏ 2p .
Commonly used methods to deal with the safety issue in relational databases are based on “placing constraint of finiteness” on relational calculus. This paper describes how safety can be achieved using a novel approach. A new representation is created to denote the relations defined by relational calculus. An algorithm which can symbolically handle infinite relations is designed to efficiently compute...
Deterministic, parallel set-term unification algorithms for higher-order logic-based database languages, of which set terms have the commutative and idempotent properties, are lacking. As a result, an efficient, deterministic inference mechanism that can be used to determine answers to queries of these database languages is non-existent. To overcome these shortcomings, we propose a set-term unification...
Closure systems C ⊂ 2Mon a finite set M arise in many areas of discrete mathematics. They are conveniently encoded by either the family Irr(C) of meet irreducible closed sets, or by implicational bases Σ. We significantly improve six (partly little known) algorithms in order to settle the problems (a),(b),... (g) listed below. In particular, the algorithm LINCLOSURE, which is well known in relational database theory, is enhanced. It appears as a subroutine in three of our algorithms. Applications in database theory, matroid theory and algebra will be pointed out...
The problem of determining the maximum number of node-disjoint subtrees of a tree T on nt nodes isomorphic to a tree S on ns nodes is shown to be solvable in time O(n s3/2 nt). The same asymptotic bounds are observed for the corresponding problems where topological imbedding and subgraph homeomorphism are respectively substituted for subgraph isomorphism.
We want to find the connected components of an unknown graph G with a known vertex set V. We learn about G by sending an oracle a query set S⊂V, and the oracle tells us the vertices connected to S. We want to use the minimum number of queries, adaptively, to find the components. The problem is also known as interconnect diagnosis of wiring networks in VLSI. The graph has n vertices and k components,...
Consider a graph in which each edge is associated with q weights. In this paper we discuss different aspects of the problem of minimizing the minimum-spanning-tree cost simultaneously with respect to the different weights.
The complexity of embedding a graph into a variety of topological surfaces is investigated. A new data structure for graph embeddings is introduced and shown to be superior to the previously known data structures. In particular, the new data structure efficiently supports all on-line operations for general graph embeddings. Based on this new data structure, very efficient algorithms are developed...
A generalization of the majority quorum for the solution of the distributed (k+1)-exclusion problem is proposed. This scheme produces a family of quorums of varying sizes and availabilities indexed by integral divisors r of k. The cases r=1 and r=k correspond to known majority based quorum generation algorithms MAJ and DIV, whereas intermediate values of r interpolate between these two extremes. A...
The main objective of data replication is to provide high availability of data for processing transactions. Quorum consensus (QC) methods are frequently applied to managing replicated data. In this paper, we present a new QC method. The proposed QC approach has a low message overhead: 1) In the best case, each transaction operation process needs only to communicate with $$O\left( {\sqrt n \log...
A Craig interpolant of two inconsistent theories is a formula which is true in one and false in the other. This paper gives an efficient method for constructing a Craig interpolant from a refutation proof which involves binary resolution, paramodulation, and factoring. This method can solve the machine learning problem of discovering a first order concept from given examples. It can also be used to...
Term rewriting system is a helpful tool for implementing functional programming languages. We focus upon a transformation of term rewriting systems called currying. Currying transforms a term rewriting system with symbols of arbitrary arity into another one, which contains only nulary symbols with a single binary symbol called application. Currying in single-sorted case is explored in [1] but currying...
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.