Minimal proper interval completions

Given an arbitrary graph G=(V,E) and a proper interval graph H=(V,F) with E⊆F we say that H is a proper interval completion of G. The graph H is called a minimal proper interval completion of G if, for any sandwich graph H^′=(V,F^′) with E⊆F^′⊂F, H^′ is not a proper interval graph. In this paper we give a O(n+m) time algorithm computing a minimal proper interval completion of an arbitrary graph. The output is a proper interval model of the completion.     

Graphs of interval count two with a given partition

We describe a polynomial time algorithm to decide for a given connected graph G and a given partition of its vertex set into two sets A and B  , whether it is possible to assign a closed interval I(u)$I(u)$ to each vertex u of G such that two distinct vertices u and v of G   are adjacent if and only if I(u)$I(u)$ and I(v)$I(v)$ intersect, all intervals assigned to vertices in A   have some length _LA$L_A$, and all intervals assigned to vertices in B   have some length _LB$L_B$ where _LA<_LB$L_A<L_B$. Our result is motivated by the interval count problem whose complexity status is open.     

A simple algorithm to find Hamiltonian cycles in proper interval graphs

We present an algorithm to find a Hamiltonian cycle in a proper interval graph in O(m+n) time, where m is the number of edges and n is the number of vertices in the graph. The algorithm is simpler and shorter than previous algorithms for the problem.     

Fast and simple algorithms to count the number of vertex covers in an interval graph

This study provides the following fast and simple algorithms for an interval graph: (1) an algorithm for counting the number of vertex covers, and (2) an algorithm for counting the number of minimal vertex covers.     

An interval type-2 fuzzy logic system-based method for prediction interval construction

This paper introduces a new non-parametric method for uncertainty quantification through construction of prediction intervals (PIs). The method takes the left and right end points of the type-reduced set of an interval type-2 fuzzy logic system (IT2FLS) model as the lower and upper bounds of a PI. No assumption is made in regard to the data distribution, behaviour, and patterns when developing intervals. A training method is proposed to link the confidence level (CL) concept of PIs to the intervals generated by IT2FLS models. The new PI-based training algorithm not only ensures that PIs constructed using IT2FLS models satisfy the CL requirements, but also reduces widths of PIs and generates practically informative PIs. Proper adjustment of parameters of IT2FLSs is performed through the minimization of a PI-based objective function. A metaheuristic method is applied for minimization of the non-linear non-differentiable cost function. Performance of the proposed method is examined for seven synthetic and real world benchmark case studies with homogenous and heterogeneous noise. The demonstrated results indicate that the proposed method is capable of generating high quality PIs. Comparative studies also show that the performance of the proposed method is equal to or better than traditional neural network-based methods for construction of PIs in more than 90% of cases. The superiority is more evident for the case of data with a heterogeneous noise.     

Computer-generated interval extensions of factorable functions and their derivatives

A simple method for obtaining computer-generated interval extensions of a real rational factorable function and its first and second partial derivatives is described, Extensions for irrational factorable functions and several applications of the techniques are discussed     

Reconstruction of interval graphs

The graph reconstruction conjecture is a long-standing open problem in graph theory. There are many algorithmic studies related to it, such as DECK CHECKING, LEGITIMATE DECK, PREIMAGE CONSTRUCTION, and PREIMAGE COUNTING. We study these algorithmic problems by limiting the graph class to interval graphs. Since we can solve GRAPH ISOMORPHISM for interval graphs in polynomial time, DECK CHECKING for interval graphs is easily done in polynomial time. Since the number of interval graphs that can be obtained from an interval graph by adding a vertex and edges incident to it can be exponentially large, developing polynomial time algorithms for LEGITIMATE DECK, PREIMAGE CONSTRUCTION, and PREIMAGE COUNTING on interval graphs is not trivial. We present that these three problems are solvable in polynomial time on interval graphs.     

A linear-time algorithm to compute a MAD tree of an interval graph

The average distance of a connected graph G is the average of the distances between all pairs of vertices of G. We present a linear time algorithm that determines, for a given interval graph G, a spanning tree of G with minimum average distance (MAD tree). Such a tree is sometimes referred to as a minimum routing cost spanning tree.     

Two-objective method for crisp and fuzzy interval comparison in optimization

In real optimization we always meet two main groups of criteria: requirements of useful outcomes increasing or expenses decreasing and demands of lower uncertainty or, in other words, risk minimization. Therefore, it seems advisable to formulate optimization problem under conditions of uncertainty, at least, two-objective on the basis of local criteria of outcomes increasing or expenses reduction and risk minimization. Generally, risk may be treated as the uncertainty of obtained result. In the considered situation, the degree of risk (uncertainty) may be defined in a natural way through the width of final interval objective function at the point of optimum achieved. To solve the given problem, the two-objective interval comparison technique has been developed taking into account the probability of supremacy of one interval over the other one and relation of compared widths of intervals. To illustrate the efficiency of the proposed method, the simple examples of minimization of interval double-extreme discontinuous cost function and fuzzy extension of Rosenbrock's test function are presented.     

Optimal interval estimation fusion based on sensor interval estimates with confidence degrees

The interval estimation fusion method based on sensor interval estimates and their confidence degrees is developed. When sensor estimates are independent of each other, a combination rule to merge sensor estimates and their confidence degrees is proposed. Moreover, two optimization criteria: minimizing interval length with an allowable minimum confidence degree, or maximizing confidence degree with an allowable maximum interval length are suggested. In terms of the two criteria, an optimal interval estimation fusion can be obtained based on the combined intervals and their confidence degrees. Then we can extend the results on the combined interval outputs and their confidence degrees to obtain a conditional combination rule and the corresponding optimal fault-tolerant interval estimation fusion in terms of the two criteria. It is easy to see that Marzullo's fault-tolerant interval estimation fusion [Marzullo, (1990). Tolerating failures of continuous-valued sensors. ACM Transactions on Computer System, 8(4), 284-304] is a special case of our method.     

特殊图的图修正问题研究综述

图修正问题是指在一个图中进行删除点、删除边或加边操作,使这个图转变成另一个具有某种特殊性质的图。图修正问题一直被广泛研究,尤其对弦图、区间图以及单位区间图的图修正问题的研究更是如此。弦图是完美图中最重要的一类图,也是(单位)区间图的父类图,很多经典的NP难问题在弦图上都是多项式可解的。区间图以及单位区间图在生物计算上有着广泛的应用。对这几类图的图修正问题的研究对计算机理论和实践有很大的贡献。首先介绍并总结了关于弦图、区间图以及单位区间图的图修正问题的重要算法和技术,然后对这些问题的研究现状进行分析,并提出了今后研究中值得关注的问题。     

On interval fuzzy S-implications

This paper presents an analysis of interval-valued S-implications and interval-valued automorphisms, showing a way to obtain an interval-valued S-implication from two S-implications, such that the resulting interval-valued S-implication is said to be obtainable. Some consequences of that are: (1) the resulting interval-valued S-implication satisfies the correctness property, and (2) some important properties of usual S-implications are preserved by such interval representations. A relation between S-implications and interval-valued S-implications is outlined, showing that the action of an interval-valued automorphism on an interval-valued S-implication produces another interval-valued S-implication.     

Bounded hairpin completion

Hairpin completion is a formal operation inspired from biochemistry. Here we consider a restricted variant of hairpin completion called bounded hairpin completion. Applied to a word encoding a single stranded molecule x such that either a suffix or a prefix of x is complementary to a subword of x, hairpin completion produces a new word z, which is a prolongation of x to the right or to the left by annealing.Although this operation is a purely mathematical one and the biological reality is just a source of inspiration, it seems rather unrealistic to impose no restriction on the length of the prefix or suffix added by the hairpin completion. The restriction considered here concerns the length of all prefixes and suffixes that are added to the current word by hairpin completion. They cannot be longer than a given constant. Closure properties of some classes of formal languages under the non-iterated and iterated bounded hairpin completion are investigated. We consider the bounded hairpin completion distance between two words and generalize this distance to languages and discuss algorithms for computing them. Finally also the inverse operation, namely bounded hairpin reduction, as well as the set of all primitive bounded hairpin roots of a regular language are considered.     

Interval additive generators of interval t-norms and interval t-conorms

The aim of this paper is to introduce the concepts of interval additive generators of interval t-norms and interval t-conorms, as interval representations of additive generators of t-norms and t-conorms, respectively, considering both the correctness and the optimality criteria. The formalization of interval fuzzy connectives in terms of their interval additive generators provides a more systematic methodology for the selection of interval t-norms and interval t-conorms in the various applications of fuzzy systems. We also prove that interval additive generators satisfy the main properties of additive generators discussed in the literature.     

Connectivity in a random interval graph with access points

We derive closed analytical formulae of connectivity for random interval graphs in the presence of fixed access points. We examine the influence of positions of access points on the graph accessible connectivity. The results developed in this paper are useful in the design and engineering of random wireless access network in the future.     

A polynomial time algorithm to detect PQI interval orders

Let S be a P Q I preference structure on a finite set A , where the relations P , Q , I stand for 'strict preference', 'weak preference' and 'indifference,' respectively. Two specific preference structures: P Q I semi orders and P Q I interval orders, have been considered and characterised recently in such a way that is possible to associate to each element of A an interval such that P holds when one interval is completely to the right of the other, I holds when one interval is included to the other and Q holds when one interval is to the right of the other, but they do have a non empty intersection ( Q medelling the hesitation). While the detection of a P Q I semiorder is straightforward, the case of the P Q I interval order is more difficult as the theorem of existence consists in a second-order formula. The paper presents an algorithm for detecting a P Q I interval order and demonstrates that it is backtracking free. This result leads to a matrix version of the algorithm which can be proved to be polynomial.     

基于知识图谱嵌入和补全的电梯故障预测

为及早预测电梯发生的常见故障,提高电梯设备的维保质量和效率,提出基于规则推理、知识图谱嵌入技术和知识图谱补全技术实现电梯故障预测的方法,在构建电梯故障知识图谱后,通过改进的组合模型将三元组中的实体和关系训练为连续的低维向量空间,实现三元组对于故障预测相关运算的兼容,通过组合模型实现电梯实体、关系和故障实体三元组的预测....