A methodology for coupling fragments of XPath with structural indexes for XML documents

We introduce a new methodology for coupling language-induced partitions and index  -induced partitions on XML documents that is aimed for the benefit of efficient evaluation of XPath queries. In particular, we identify XPath fragments which are ideally coupled with the newly introduced P(k)$P(k)$-partition which has its definition grounded in the well-known A(k)$A(k)$ structural index and its associated partition. We then utilize these couplings to investigate fundamental questions about the use of structural indexes in XPath query evaluation.     

Computing phylogenetic roots with bounded degrees and errors is NP-complete

In this paper we study the computational complexity of the following optimization problem: given a graph G=(V,E)$G=(V,E)$, we wish to find a tree T such that (1) the degree of each internal node of T   is at least 3 and at most Δ$\Delta$, (2) the leaves of T are exactly the elements of V, and (3) the number of errors, that is, the symmetric difference between E   and {{u,v}:u,v$\{\{u,v\}:u,v$ are leaves of T   and _dT(u,v)≤k}$d_T(u,v)\le k\}$, is as small as possible, where _dT(u,v)$d_T(u,v)$ denotes the distance between u$u$ and v$v$ in tree T  . We show that this problem is NP-hard for all fixed constants Δ,k≥3$\Delta ,k\ge 3$.     

Extended dominance and a stochastic shortest path problem

In the context of stochastic networks, we study the problem of finding a path P   that combines in a reasonable way the mean m(P)$m(P)$ and variance v(P)$v(P)$ of its length. Specifically we study a separable objective function that combines these two path measures: namely, z(P)=f(m(P))+g(v(P))$z(P)=f(m(P))+g(v(P))$, where f$f$ is an increasing convex function and g is an increasing concave function. A new type of dominance (e-dominance), stronger than the standard form of dominance, is then introduced, and it is shown to satisfy a certain form of Bellman's optimality principle. This means that it is possible to modify existing label-setting and label-correcting methods by using e-dominance, and without sacrificing optimality. Computational experience with these enhanced labeling algorithms has been promising. Test results for a variety of sample problems show that the e-dominance criterion can often significantly reduce the number of nondominated path vectors, compared to the standard dominance criterion. We observe a consequent reduction in both computation time and storage requirements.     

A polynomial-time algorithm for computing K-terminal residual reliability of d-trapezoid graphs

Consider a probabilistic graph G   in which the edges of E(G)$E(G)$ are perfectly reliable, but the vertices of V(G)$V(G)$ may fail with some known probabilities. Given a subset K   of V(G)$V(G)$, the K-terminal residual reliability of G is the probability that all operational vertices in K are connected to each other. This problem can be considered to be a generalization of two well-known reliability problems – the K-terminal reliability problem and the residual connectedness reliability problem.     

A sufficient condition involving implicit degree and neighborhood intersection for long cycles

Let id(v)$\mathit{id}(v)$ denote the implicit degree of a vertex v in a graph G. In this paper, we prove that: Let G   be a 2-connected graph. If max?{id(u),id(v)}≥c/2$\max ?\{\mathit{id}(u),\mathit{id}(v)\}\ge c/2$ for each pair of nonadjacent vertices u and v   in an induced claw, and |N(x)∩N(y)|≥2$|N(x)\cap N(y)|\ge 2$ for each pair of nonadjacent vertices x and y in an induced modified claw, then G contains either a hamiltonian cycle or a cycle of length at least c.     

A concurrent lambda calculus with futures

We introduce a new lambda calculus with futures, λ(fut)$\lambda (\mathsf{fut})$, that models the operational semantics of concurrent statically typed functional programming languages with mixed eager and lazy threads such as Alice ML, a concurrent extension of Standard ML. λ(fut)$\lambda (\mathsf{fut})$ is a minimalist extension of the call-by-value λ$\lambda$-calculus that is sufficiently expressive to define and combine a variety of standard concurrency abstractions, such as channels, semaphores, and ports. Despite its minimality, the basic machinery of λ(fut)$\lambda (\mathsf{fut})$ is sufficiently powerful to support explicit recursion and call-by-need evaluation.     

First steps to the runtime complexity analysis of ant colony optimization

The paper presents results on the runtime complexity of two ant colony optimization (ACO) algorithms: ant system, the oldest ACO variant, and GBAS, the first ACO variant for which theoretical convergence results have been established. In both cases, as the class of test problems under consideration, a slight generalization of the well-known OneMax test function has been chosen. The techniques used for the runtime analysis of the two algorithms differ: in the case of GBAS, the expected runtime until the optimal solution is reached is studied by a direct bound estimation approach inspired by comparable results for the (1+1)$(1+1)$ evolutionary algorithm (EA). A runtime bound of order O(mlogm)$O(m\log m)$, where m   is the problem instance size, is obtained. In the case of ant system, the original discrete stochastic process is approximated by a suitable continuous deterministic process. The validity of the approximation is shown by means of a rigid convergence theorem exploiting a classical result from mathematical learning theory. Using this approximation, it is demonstrated that for the considered OneMax-type problems, a runtime of order O(mlog(1/ε))$O(m\log (1/\epsilon ))$ until reaching an expected relative   solution quality of 1-ε$1-\epsilon$, and a runtime of O(mlogm)$O(m\log m)$ until reaching the optimal   solution with high probability can be predicted. Our results are the first to show competitiveness in runtime complexity with (1+1$1+1$) EA on OneMax for a proper ACO algorithm.     

A simple optimal representation for balanced parentheses

We consider succinct, or highly space-efficient, representations of a (static) string consisting of n   pairs of balanced parentheses, which support natural operations such as finding the matching parenthesis for a given parenthesis, or finding the pair of parentheses that most tightly enclose a given pair. This problem was considered by Jacobson [Space-efficient static trees and graphs, in: Proc. of the 30th FOCS, 1989, pp. 549–554] and Munro and Raman [Succinct representation of balanced parentheses and static trees, SIAM J. Comput. 31 (2001) 762–776] who gave O(n)$\mathrm{O}(n)$-bit and 2n+o(n)$2n+\mathrm{o}(n)$-bit representations, respectively, that supported the above operations in O(1)$\mathrm{O}(1)$ time on the RAM model of computation. This data structure is a fundamental tool in succinct representations, and has applications in representing suffix trees, ordinal trees, planar graphs and permutations.     

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.     

Divergence bounded computable real numbers

A real x$x$ is called h$h$-bounded computable  , for some function h:N→N$h:\mathbb{N}\to \mathbb{N}$, if there is a computable sequence (_xs)$(x_s)$ of rational numbers which converges to x$x$ such that, for any n∈N$n\in \mathbb{N}$, at most h(n)$h(n)$ non-overlapping pairs of its members are separated by a distance larger than 2^-n$2^{-n}$. In this paper we discuss properties of h$h$-bounded computable reals for various functions h$h$. We will show a simple sufficient condition for a class of functions h$h$ such that the corresponding h$h$-bounded computable reals form an algebraic field. A hierarchy theorem for h$h$-bounded computable reals is also shown. Besides we compare semi-computability and weak computability with the h$h$-bounded computability for special functions h$h$.     

MinT—Architecture and applications of the (t, m, s)-net and OOA database

Many different constructions for (t,m,s)$(t\text{,}m\text{,}s)$-nets and (t,s)$(t\text{,}s)$-sequences are known today. Propagation rules as well as connections to other mathematical objects make it difficult to determine the best net available in a given setting.     

Notes on a conjecture of Manoussakis concerning Hamilton cycles in digraphs

In 1992, Manoussakis conjectured that a strongly 2-connected digraph D on n vertices is hamiltonian if for every two distinct pairs of independent vertices x, y and w, z   we have d(x)+d(y)+d(w)+d(z)≥4n−3$d(x)+d(y)+d(w)+d(z)\ge 4n-3$. In this note we show that D has a Hamilton path, which gives an affirmative evidence supporting this conjecture.     

Bounded Budget Connection (BBC) games or how to make friends and influence people,on a budget

Motivated by applications in social and peer-to-peer networks, we introduce the Bounded Budget Connection (BBC) game and study its pure Nash equilibria. We have a collection of n   players, each with a budget for purchasing links. Each link has a cost and a length. Each node has a preference weight for each node, and its objective is to purchase outgoing links within its budget to minimize its sum of preference-weighted distances to the nodes. We show that determining if a BBC game has pure Nash equilibria is NP-hard. We study (n,k)$(n,k)$-uniform BBC games, where all link costs, lengths, and preferences are equal and every budget equals k  . We show that pure Nash equilibria exist for all (n,k)$(n,k)$-uniform BBC games and all equilibria are essentially fair. We construct a family of equilibria spanning the spectrum from minimum to maximum social cost. We also analyze best-response walks and alternative node objectives.     

(r|p)-centroid problems on networks with vertex and edge demand

This paper analyzes (r|p)-centroid$(r|p)\mathrm{-}\mathrm{centroid}$ problems on networks with vertex and edge demand under a binary choice rule. Bilevel programming models are presented for the discrete problem class. Furthermore, NP-hardness proofs for the discrete and continuous (1|p)-centroid$(1|p)\mathrm{-}\mathrm{centroid}$ problem on general networks with edge demand only are provided. Nevertheless, an efficient algorithm to determine a discrete (1|p)-centroid$(1|p)\mathrm{-}\mathrm{centroid}$ of a tree network with vertex and edge demand can be derived.     

Topological additive numbering of directed acyclic graphs

We propose to study a problem that arises naturally from both Topological Numbering of Directed Acyclic Graphs, and Additive Coloring (also known as Lucky Labeling). Let D be a digraph and f   a labeling of its vertices with positive integers; denote by S(v)$S(v)$ the sum of labels over all neighbors of each vertex v. The labeling f is called topological additive numbering   if S(u)<S(v)$S(u)<S(v)$ for each arc (u,v)$(u,v)$ of the digraph. The problem asks to find the minimum number k for which D   has a topological additive numbering with labels belonging to {1,…,k}$\{1,\dots ,k\}$, denoted by _ηt(D)${\eta }_t(D)$.     

On hypercube packings,blocking sets and a covering problem

Consider sets S of hypercubes of side 2 in the discrete n-dimensional torus of side 4 with the property that every possible hypercube of side 2 has a nonempty intersection with some hypercube in S. The problem of minimizing the size of S is studied in two settings, depending on whether intersections between hypercubes in S are allowed or not. If intersections are not allowed, then one is asking for the smallest size of a non-extensible packing S  ; this size is denoted by f(n)$f(n)$. If intersections are allowed, then the structure S is called a blocking set. The smallest size of a blocking set S   is denoted by h(n)$h(n)$. By computer-aided techniques, it is shown that f(5)=12$f(5)=12$, f(6)=16$f(6)=16$, h(6)=15$h(6)=15$ and h(7)≤23$h(7)\le 23$. Also, non-extensible packings as well as blocking sets of certain small sizes are classified for n≤6$n\le 6$. There is a direct connection between these problems and a covering problem originating from the football pools.     

On the partition dimension of a class of circulant graphs

For a vertex v   of a connected graph G(V,E)$G(V,E)$ and a subset S of V, the distance between a vertex v and S   is defined by d(v,S)=min{d(v,x):x∈S}$d(v,S)=\min \{d(v,x):x\in S\}$. For an ordered k  -partition π={_S1,_S2…_Sk}$\pi =\{S_1,S_2\dots S_k\}$ of V, the partition representation of v with respect to π is the k  -vector r(v|π)=(d(v,_S1),d(v,_S2)…d(v,_Sk))$r(v|\pi )=(d(v,S_1),d(v,S_2)\dots d(v,S_k))$. The k-partition π is a resolving partition if the k  -vectors r(v|π)$r(v|\pi )$, v∈V(G)$v\in V(G)$ are distinct. The minimum k for which there is a resolving k-partition of V is the partition dimension of G. Salman et al. [1] in their paper which appeared in Acta Mathematica Sinica, English Series   proved that partition dimension of a class of circulant graph G(n,±{1,2})$G(n,\pm \{1,2\})$, for all even n?6$n?6$ is four. In this paper we prove that it is three.