On Graph-Based Cryptography and Symbolic Computations

We have been investigating the cryptographical properties of in nite families of simple graphs of large girth with the special colouring of vertices during the last 10 years. Such families can be used for the development of cryptographical algorithms (on symmetric or public key modes) and turbocodes in error correction theory. Only few families of simple graphs of large unbounded girth and arbitrarily large degree are known. The paper is devoted to the more general theory of directed graphs of large girth and their cryptographical applications. It contains new explicit algebraic constructions of in finite families of such graphs. We show that they can be used for the implementation of secure and very fast symmetric encryption algorithms. The symbolic computations technique allow us to create a public key mode for the encryption scheme based on algebraic graphs.

On Finite Element Methods for 2nd order (semi–) periodic Eigenvalue Problems

We deal with a class of elliptic eigenvalue problems (EVPs) on a rectangle Ω ⊂ R^2 , with periodic or semi–periodic boundary conditions (BCs) on ∂Ω. First, for both types of EVPs, we pass to a proper variational formulation which is shown to fit into the general framework of abstract EVPs for symmetric, bounded, strongly coercive bilinear forms in Hilbert spaces, see, e.g., [13, §6.2]. Next, we consider finite element methods (FEMs) without and with numerical quadrature. The aim of the paper is to show that well–known error estimates, established for the finite element approximation of elliptic EVPs with classical BCs, hold for the present types of EVPs too. Some attention is also paid to the computational aspects of the resulting algebraic EVP. Finally, the analysis is illustrated by two non-trivial numerical examples, the exact eigenpairs of which can be determined.

Some Computational Aspects of the Consistent Mass Finite Element Method for a (semi-)periodic Eigenvalue Problem

We consider a model eigenvalue problem (EVP) in 1D, with periodic or semi–periodic boundary conditions (BCs). The discretization of this type of EVP by consistent mass finite element methods (FEMs) leads to the generalized matrix EVP Kc = λ M c, where K and M are real, symmetric matrices, with a certain (skew–)circulant structure. In this paper we fix our attention to the use of a quadratic FE–mesh. Explicit expressions for the eigenvalues of the resulting algebraic EVP are established. This leads to an explicit form for the approximation error in terms of the mesh parameter, which confirms the theoretical error estimates, obtained in [2].

The Application of Graph Model for Automation of the User Interface Construction

The ability of automatic graphic user interface construction is described. It is based on the building of user interface as reflection of the data domain logical definition. The submitted approach to development of the information system user interface enables dynamic adaptation of the system during their operation. This approach is used for creation of information systems based on CASE-system METAS.

The Development of Parallel Resolution Algorithms Using the Graph Representation

The parallel resolution procedures based on graph structures method are presented. OR-, AND- and DCDP- parallel inference on connection graph representation is explored and modifications to these algorithms using heuristic estimation are proposed. The principles for designing these heuristic functions are thoroughly discussed. The colored clause graphs resolution principle is presented. The comparison of efficiency (on the Steamroller problem) is carried out and the results are presented. The parallel unification algorithm used in the parallel inference procedure is briefly outlined in the final part of the paper.

Cultural Knowledge for Named Entity Disambiguation: A Graph-Based Semantic Relatedness Approach

One of the ultimate aims of Natural Language Processing is to automate the analysis of the meaning of text. A fundamental step in that direction consists in enabling effective ways to automatically link textual references to their referents, that is, real world objects. The work presented in this paper addresses the problem of attributing a sense to proper names in a given text, i.e., automatically associating words representing Named Entities with their referents. The method for Named Entity Disambiguation proposed here is based on the concept of semantic relatedness, which in this work is obtained via a graph-based model over Wikipedia. We show that, without building the traditional bag of words representation of the text, but instead only considering named entities within the text, the proposed method achieves results competitive with the state-of-the-art on two different datasets.

The Eccentric Connectivity Polynomial of some Graph Operations

The eccentric connectivity index of a graph G, ξ^C, was proposed by Sharma, Goswami and Madan. It is defined as ξ^C(G) = ∑ u ∈ V(G) degG(u)εG(u), where degG(u) denotes the degree of the vertex x in G and εG(u) = Max{d(u, x) | x ∈ V (G)}. The eccentric connectivity polynomial is a polynomial version of this topological index. In this paper, exact formulas for the eccentric connectivity polynomial of Cartesian product, symmetric difference, disjunction and join of graphs are presented.

Statistical Numerical Methods for Eigenvalue Problem. Parallel Implementation

MSC subject classification: 65C05, 65U05.

On Principle Eigenvalue for Linear Second Order Elliptic Equations in Divergence Form

2002 Mathematics Subject Classification: 35J15, 35J25, 35B05, 35B50

The Asymptotic Behaviour of the First Eigenvalue of Linear Second-Order Elliptic Equations in Divergente Form

2000 Mathematics Subject Classification: 35J70, 35P15.