In the framework of models generated by compositional expressions, we solve two topical marginalization problems (namely, the single-marginal problem and the marginal-representation problem) that were solved only for the special class of the so-called “canonical expressions”. We also show that the two problems can be solved “from scratch” with preliminary symbolic computation.
A buttoning of a tree that has vertices v1, v2, . . . , vn is a closed walk that starts at v1 and travels along the shortest path in the tree to v2, and then along the shortest path to v3, and so forth, finishing with the shortest path from vn to v1. Inspired by a problem about buttoning a shirt inefficiently, we determine the maximum length of buttonings of trees
An (f, g)-semi-matching in a bipartite graph G = (U ∪ V,E) is a set of edges M ⊆ E such that each vertex u ∈ U is incident with at most f(u) edges of M, and each vertex v ∈ V is incident with at most g(v) edges of M. In this paper we give an algorithm that for a graph with n vertices and m edges, n ≤ m, constructs a maximum (f, g)-semi-matching in running time O(m ⋅ min [...] ) Using the reduction of [5] our result on maximum (f, g)-semi-matching problem directly implies an algorithm for the optimal...
We provide an algorithm for listing all minimal 2-dominating sets of a tree of order n in time 𝒪(1.3248n). This implies that every tree has at most 1.3248n minimal 2-dominating sets. We also show that this bound is tight.
We present briefly some results we obtained with known methods to solve minimum cost tension problems, comparing their performance on non-specific graphs and on series-parallel graphs. These graphs are shown to be of interest to approximate many tension problems, like synchronization in hypermedia documents. We propose a new aggregation method to solve the minimum convex piecewise linear cost tension problem on series-parallel graphs in operations.
We present briefly some results we obtained with known methods to solve minimum cost tension problems, comparing their performance on non-specific graphs and on series-parallel graphs. These graphs are shown to be of interest to approximate many tension problems, like synchronization in hypermedia documents. We propose a new aggregation method to solve the minimum convex piecewise linear cost tension problem on series-parallel graphs in O(m3) operations.
Let G be an undirected graph with n vertices. Assume that a robot is placed on a vertex and n − 2 obstacles are placed on the other vertices. A vertex on which neither a robot nor an obstacle is placed is said to have a hole. Consider a single player game in which a robot or obstacle can be moved to adjacent vertex if it has a hole. The objective is to take the robot to a fixed destination vertex using minimum number of moves. In general, it is not necessary that the robot will take a shortest path...