Crown graphs and subdivision of ladders are odd graceful

A graph G of size q is odd graceful, if there is an injection φ from V(G) to {0, 1, 2, …, 2q?1} such that, when each edge xy is assigned the label or weight |f(x)?f(y)|, the resulting edge labels are {1, 3, 5, …, 2q?1}. This definition was introduced in 1991 by Gnanajothi [3], who proved that the graphs obtained by joining a single pendant edge to each vertex of C _n are odd graceful, if n is even. In this paper, we generalize Gnanajothi's result on cycles by showing that the graphs obtained by joining m pendant edges to each vertex of C _n are odd graceful if n is even. We also prove that the subdivision of ladders S(L _n ) (the graphs obtained by subdividing every edge of L _n exactly once) is odd graceful.     

Constraint acquisition for Entity-Relationship models

We establish search algorithms from the area of propositional logic as invaluable tools for the semantic knowledge acquisition in the conceptual database design phase. The acquisition of such domain knowledge is crucial for the quality of the target database.Integrity constraints are conditions that capture the semantics of the application domain under consideration. They restrict the databases to those that are considered meaningful to the application at hand. In practice, the decision of specifying a constraint is very important and extremely challenging.We show how techniques from propositional logic can be utilised to offer decision support for specifying Boolean and multivalued dependencies between properties of entities and relationships in conceptual databases. In particular, we use a search version of SAT-solvers to semi-automatically generate sample databases for this class of dependencies in Entity-Relationship models. The sample databases enable design participants to judge, justify, convey and test their understanding of the semantics of the future database. Indeed, the decision by the participants to specify a dependency explicitly is reduced to their decision whether there is some sample database that they can accept as a future database instance.     

Farey graphs as models for complex networks

Farey sequences of irreducible fractions between 0 and 1 can be related to graph constructions known as Farey graphs. These graphs were first introduced by Matula and Kornerup in 1979 and further studied by Colbourn in 1982, and they have many interesting properties: they are minimally 3-colorable, uniquely Hamiltonian, maximally outerplanar and perfect. In this paper, we introduce a simple generation method for a Farey graph family, and we study analytically relevant topological properties: order, size, degree distribution and correlation, clustering, transitivity, diameter and average distance. We show that the graphs are a good model for networks associated with some complex systems.     

Efficient energy-based embedding models for link prediction in knowledge graphs

We focus on the problem of link prediction in Knowledge Graphs, with the goal of discovering new facts. To this purpose, Energy-Based Models for Knowledge Graphs that embed entities and relations in continuous vector spaces have been largely used. The main limitation in their applicability lies in the parameter learning phase, which may require a large amount of time for converging to optimal solutions. In this article, we first propose an unified view on different Energy-Based Embedding Models. Hence, for improving the model training phase, we propose the adoption of adaptive learning rates. We show that, by adopting adaptive learning rates during training, we can improve the efficiency of the parameter learning process by an order of magnitude, while leading to more accurate link prediction models in a significantly lower number of iterations. We extensively evaluate the proposed learning procedure on a variety of new models: our result show a significant improvement over state-of-the-art link prediction methods on two large Knowledge Graphs, namely WordNet and Freebase.     

Cayley graphs as models of deterministic small-world networks

Many real networks, including those in social, technological, and biological realms, are small-world networks. The two distinguishing characteristics of small-world networks are high local clustering and small average internode distance. A great deal of previous research on small-world networks has been based on probabilistic methods, with a rather small number of researchers advocating deterministic models. In this paper, we further the study of deterministic small-world networks and show that Cayley graphs may be good models for such networks. Small-world networks based on Cayley graphs possess simple structures and significant adaptability. The Cayley-graph model has pedagogical value and can also be used for designing and analyzing communication and the other real networks.     

Constructing structural VAR models with conditional independence graphs

In this paper graphical modelling is used to select a sparse structure for a multivariate time series model of New Zealand interest rates. In particular, we consider a recursive structural vector autoregressions that can subsequently be described parsimoniously by a directed acyclic graph, which could be given a causal interpretation. A comparison between competing models is then made by considering likelihood and economic theory.     

Using Constraint Programming in Selection Operators for Constraint Databases

Constraint Databases represent complex data by means of formulas described by constraints (equations, inequations or Boolean combinations of both). Commercial database management systems allow the storage and efficient retrieval of classic data, but for complex data a made-to-measure solution combined with expert systems for each type of problem are necessary. Therefore, in the same way as commercial solutions of relational databases permit storing and querying classic data, we propose an extension of the Selection Operator for complex data stored, and an extension of SQL language for the case where both classic and constraint data need to be managed. This extension shields the user from unnecessary details on how the information is stored and how the queries are evaluated, thereby enlarging the capacity of expressiveness for any commercial database management system. In order to minimize the selection time, a set of strategies have been proposed, which combine the advantages of relational algebra and constraint data representation.     

Achieving graceful performance in distributed error-prone databases

Data availability is an important requirement of distributed databases. Replication is a technique that has been proposed to meet this need. In the absence of failures, traditional replica control algorithms provide complete availability in the sense that any transaction can be executed. The worst case of data availability occurs when the system is totally partitioned (each operational site is isolated from every other site). In this paper, we present techniques to achieve high availability under combinations of site failures and partitions. Users are required to specify the database access requirements in the totally-partitioned environment. This information is represented by means of a Read Access Graph (RAG). When failures occur, the set of items that may be accessed by a transaction depends on the connectivity of the network and the RAG. The techniques ensure that as failures occur the loss of availability is gradual and graceful. Data availability improves with the level of normalcy in the system. Unless there is a complete failure, at least some predefined set of transactions can be executed. It is shown that these algorithms preserve the integrity of the database by ensuring that all executions are one-copy serializable. The algorithms compare favorably with other replica management schemes in terms of availability. K. Brahmadathan obtained a Bachelor's degree in Electronics and Communications Engineering from University of Kerala, Trivandrum, India; a Master's degree in Computer Science from Indian Institute of Technology, Madras, India; and the M.S. and Ph.D. degrees in Computer Science from University of Pittsburgh. Since 1989, he has been an Assistant Professor of Computer Science at the University of Wyoming. His research interests are in the areas of database systems and distributed systems. K.V.S. Ramarao obtained his M.Sc. in Applied Mathematics from Andhra University, Waltair, India; M.Tech. in Computer Science from IIT Kanpur, India; and the Ph.D. in Computing Science from University of Alberta, Edmonton, Canada. He is currently a Senior Technologist for Southwestern Bell Technology Resources, Inc. Prior to that, he was an Assistant Professor at the University of Pittsburgh. His current research interests include distributed systems and distributed databases.     

Constraint solving for interpolation

Interpolation is an important component of recent methods for program verification. It provides a natural and effective means for computing the separation between the sets of ‘good’ and ‘bad’ states. The existing algorithms for interpolant generation are proof-based: They require explicit construction of proofs, from which interpolants can be computed. Construction of such proofs is a difficult task. We propose an algorithm for the generation of interpolants for the combined theory of linear arithmetic and uninterpreted function symbols that does not require a priori constructed proofs to derive interpolants. It uses a reduction of the problem to constraint solving in linear arithmetic, which allows application of existing highly optimized Linear Programming solvers in a black-box fashion. We provide experimental evidence of the practical applicability of our algorithm.     

Shaped lattice graphs as models of the multiprocessor computer systems

A new family of the uniform ordinary graphs named the shaped lattice graphs was proposed and studied. As applied to the structural modeling of the multiprocessor computer systems, they have two useful characteristics such as high flexibility at choosing their size (number of vertices) and possibility of obtaining small (down to d = 2) diameters independently of the graph size. The method of cycle definition and transformation by the ring sequences of edge weights, which was previously proposed for the binary hypercubes and other Cayley graphs, was extended to the shaped lattice graphs.Translated from Avtomatika i Telemekhanika, No. 3, 2005, pp. 169–180.Original Russian Text Copyright © 2005 by Parkhomenko.This paper was recommended for publication by P.Yu. Chebotarev, a member of the Editorial Board     

Estimation of graphical models whose conditional independence graphs are interval graphs and its application to modelling linkage disequilibrium

Estimation of graphical models whose conditional independence graph comes from the general class of decomposable graphs is compared with estimation under the more restrictive assumption that the graphs are interval graphs. This restriction is shown to improve the mixing of the Markov chain Monte Carlo search to find an optimal model with little effect on the haplotype frequencies implied by the estimates. A further restriction requiring intervals to cover specified points is also considered and shown to be appropriate for modelling associations between alleles at genetic loci. As well as usefully describing the patterns of associations, these estimates can also be used to model population haplotype frequencies in statistical gene mapping methods such as linkage analysis and association studies.     

基于动态约束网络的约束优化分解

约束网络通过对较大规模的任务和问题的分解,传递了并行工程产品开发过程中的各多功能小组之间必然存在的相互制约、相互依赖的关系。在任务和问题简单分解的过程中,由于所得到的子问题之间通常是不能完全独立的,因而只能在有限程度上降低难度、简化问题。在分析了约束求解的研究现状和不足的基础上,提出了一种基于动态约束的约束优化分解方法,使得各个子任务、子问题间的关系得到进一步的分解,从而在满足原要求的基础上,得到优化的结果。     

Nonlocal variational image segmentation models on graphs using the Split Bregman

Variational functionals such as Mumford-Shah and Chan-Vese methods have a major impact on various areas of image processing. After over 10 years of investigation, they are still in widespread use today. These formulations optimize contours by evolution through gradient descent, which is known for its overdependence on initialization and the tendency to produce undesirable local minima. In this paper, we propose an image segmentation model in a variational nonlocal means framework based on a weighted graph. The advantages of this model are twofold. First, the convexity global minimum (optimum) information is taken into account to achieve better segmentation results. Second, the proposed global convex energy functionals combine nonlocal regularization and local intensity fitting terms. The nonlocal total variational regularization term based on the graph is able to preserve the detailed structure of target objects. At the same time, the modified local binary fitting term introduced in the model as the local fitting term can efficiently deal with intensity inhomogeneity in images. Finally, we apply the Split Bregman method to minimize the proposed energy functional efficiently. The proposed model has been applied to segmentation of real medical and remote sensing images. Compared with other methods, the proposed model is superior in terms of both accuracy and efficient.     

Some Challenges for Constraint Programming

We propose a number of challenges for future constraint programming systems, including improvements in implementation technology (using global analysis based optimization and parallelism), debugging facilities, and the extension of the application domain to distributed, global programming. We also briefly discuss how we are exploring techniques to meet these challenges in the context of the development of the CIAO constraint logic programming system.     

Constraint Solving for Proof Planning

Proof planning is an application of AI planning to theorem proving that employs plan operators that encapsulate mathematical proof techniques. Many proofs require the instantiation of variables; that is, mathematical objects with certain properties have to be constructed. This is particularly difficult for automated theorem provers if the instantiations have to satisfy requirements specific for a mathematical theory, for example, for finite sets or for real numbers, because in this case unification is insufficient for finding a proper instantiation. Often, constraint solving can be employed for this task. We describe a framework for the integration of constraint solving into proof planning that combines proof planners and stand-alone constraint solvers. Proof planning has some peculiar requirements that are not met by any off-the-shelf constraint-solving system. Therefore, we extended an existing propagation-based constraint solver in a generic way. This approach generalizes previous work on tackling the problem. It provides a more principled way and employs existing AI technology.