A celebrated theorem of Tutte shows that the order of the vertex-stabiliser in a connected 3-valent arc-transitive graph does not exceed 48. It has long been known that no such bound exists in the broader context of connected 3-valent vertex-transitive graphs. In fact, several families of such graph in which the order of the vertex-stabiliser grows exponentially with the number of vertices were known. In this paper, we prove a surprising fact which shows that with the exception of these well understood families, in all other connected 3-valent vertex-transitive graphs the order of the vertex-stabiliser can be bounded above by a sublinear function of the order of the graph.
COBISS.SI-ID: 1537132228
We propose Jacobi-Davidson type methods for polynomial two-parameter eigenvalue problems (PMEP). Such problems can be linearized as singular two-parameter eigenvalue problems, whose matrices are of dimension $k(k+1)n/2$, where $k$ is the degree of the polynomial and $n$ is the size of the matrix coefficients in the PMEP. When $k^2n$ is relatively small, the problem can be solved numerically by computing the common regular part of the related pair of singular pencils. For large $k^2n$, computing all solutions is not feasible and iterative methods are required. When $k$ is large, we propose to linearize the problem first and then apply Jacobi-Davidson to the obtained singular two-parameter eigenvalue problem. The resulting method may for instance be used for computing zeros of a system of scalar bivariate polynomials close to a given target. On the other hand, when $k$ is small, we can apply a Jacobi-Davidson type approach directly to the original matrices. The original matrices are projected onto a low-dimensional subspace, and the projected polynomial two-parameter eigenvalue problems are solved by a linearization.
COBISS.SI-ID: 17318745
The node set of a two-mode network consists of two disjoint subsets and all its links are linking these two subsets. The links can be weighted. We developed a new method for identifying important subnetworks in two-mode networks. The method combines and extends the ideas from generalized cores in one-mode networks and from $(p, q)$-cores for two-mode networks. In this paper we introduce the notion of generalized two-mode cores and discuss some of their properties. An efficient algorithm to determine generalized two-mode cores and an analysis of its complexity are also presented. For illustration some results obtained in analyses of real-life data are presented.
COBISS.SI-ID: 17369177
We illustrate solving the protein alignment problem exactly using the algorithm VESPA (very efficient search for protein alignment). We have compared our result with the approximate solution obtained with BLAST (basic local alignment search tool) software, which is currently the most widely used for searching for protein alignment. We have selected human and mouse proteins having around 170 amino acids for comparison. The exact solution has found 78 pairs of amino acids, to which one should add 17 individual amino acid alignments giving a total of 95 aligned amino acids. BLAST has identified 64 aligned amino acids which involve pairs of more than two adjacent amino acids. However, the difference between the two outputs is not as large as it may appear, because a number of amino acids that are adjacent have been reported by BLAST as single amino acids. So if one counts all amino acids, whether isolated (single) or in a group of two and more amino acids, then the count for BLAST is 89 and for VESPA is 95, a difference of only six.
COBISS.SI-ID: 5849370
Eff is a programming language based on the algebraic approach to computational effects, in which effects are viewed as algebraic operations and effect handlers as homomorphisms from free algebras. Eff supports first-class effects and handlers through which we may easily define new computational effects, seamlessly combine existing ones, and handle them in novel ways. We give a denotational semantics of Eff and discuss a prototype implementation based on it. Through examples we demonstrate how the standard effects are treated in Eff, and how Eff supports programming techniques that use various forms of delimited continuations, such as backtracking, breadth-first search, selection functionals, cooperative multi-threading, and others.
COBISS.SI-ID: 17192025