In a typical maximum clique search algorithm when optimality testing is inconclusive a forking takes place. The instance is divided into smaller ones. This is the branching step of the procedure. In order to ensure a balanced work load for the processors for parallel algorithms it is essential that the resulting smaller problems are do not overly vary in difficulty. The so-called splitting partitions of the nodes of the given graph were introduced earlier to meliorate this problem. The paper proposes a splitting partition of the edges for the same purpose. In the lack of available theoretical tools we assess the practical feasibility of constructing suboptimal splitting edge partitions by carrying out numerical experiments. While working with splitting partitions we have realized that they can be utilized as preconditioning tools preliminary to a large scale clique search. The paper will discuss this new found role of the splitting edge partitions as well.
We prove that for any collection F of n ≥ 2 pairwise disjoint compact convex sets in the plane there is a pair of sets A and B in F such that any line that separates A from B separates either A or B from a subcollection of F with at least n/18 sets.
In this paper, we study the existence of positive solutions for a system of nonlinear fractional differential equations. The results are based upon the fixed-point theorem of cone expansion and compression type due to Krasnosel’skill. Moreover, Our results generalize and include some known results.
Criteria for a diffeomorphism of a smooth manifold M to be lifted to a linear automorphism of a given real vector bundle p : V → M, are stated. Examples are included and the metric and complex vector-bundle cases are also considered.
Let X be an irreducible complex projective variety of dimension n ≥ 1. Let D be a Cartier divisor on X such that Hi(X, OX (mD)) = 0 for m > 0 and for all i > 0, then it is not true in general that D is a nef divisor (cf. ). Also, in general, effective divisors on smooth surfaces are not necessarily nef (they are nef provided they are semiample). In this article, we show that, if X is a smooth surface of general type and C is a smooth hyperplane section of it, then for any non-zero effective divisor D on X satisfying H1(X, OX (mD)) = 0 for all m > C.KX, D is a nef divisor.
In this paper, we introduce the notion of a Gel’fand Γ-semiring and discuss the various characterization of simple, k-ideal, strong ideal, t-small elements and additively cancellative elements of a Gel’fand Γ-semiring R, and prove that the set of additively cancellative elements, set of all t-small elements of R and set of all maximal ideal of R are strong ideals. Further, let R be a simple Gel’fand Γ-semiring and 1 ≠ t ∈ R. Let M be the set of all maximal left (right) ideals of R. Then an element x of R is t-small if and only if it belongs to every maximal one sided left (right)ideal of R containing t.
For a continuous and positive function w(λ), λ > 0 and μ a positive measure on (0, ∞) we consider the following integral transform
where the integral is assumed to exist for t > 0.
We show among others that D(w, μ) is operator convex on (0, ∞). From this we derive that, if f : [0, ∞) → R is an operator monotone function on [0, ∞), then the function [f(0) -f(t)] t-1 is operator convex on (0, ∞). Also, if f : [0, ∞) → R is an operator convex function on [0, ∞), then the function is operator convex on (0, ∞). Some lower and upper bounds for the Jensen’s difference
under some natural assumptions for the positive operators A and B are given. Examples for power, exponential and logarithmic functions are also provided.
Problem 2 of Welsh’s 1976 text Matroid Theory, asking for criteria telling when two families of sets have a common transversal, is solved.
Another unsolved problem in the text Matroid Theory, on whether the “join” of two non-decreasing submodular functions is submodular, is answered in the negative. This resolves an issue first raised by Pym and Perfect in 1970.
With distributed computing and mobile applications becoming ever more prevalent, synchronizing diverging replicas of the same data is a common problem. Reconciliation – bringing two replicas of the same data structure as close as possible without overriding local changes – is investigated in an algebraic model. Our approach is to consider two sequences of simple commands that describe the changes in the replicas compared to the original structure, and then determine the maximal subsequences of each that can be propagated to the other. The proposed command set is shown to be functionally complete, and an update detection algorithm is presented which produces a command sequence transforming the original data structure into the replica while traversing both simultaneously. Syntactical characterization is provided in terms of a rewriting system for semantically equivalent command sequences. Algebraic properties of sequence pairs that are applicable to the same data structure are investigated. Based on these results the reconciliation problem is shown to have a unique maximal solution. In addition, syntactical properties of the maximal solution allow for an efficient algorithm that produces it.