The Hamilton circuit problem on grids
The influence of random number generators on graph partitioning algorithms.
The inverse maximum flow problem considering l∞ norm
The problem is to modify the capacities of the arcs from a network so that a given feasible flow becomes a maximum flow and the maximum change of the capacities on arcs is minimum. A very fast O(m⋅log(n)) time complexity algorithm for solving this problem is presented, where m is the number of arcs and n is the number of nodes of the network. The case when both, lower and upper bounds of the flow can be modified so that the given feasible flow becomes a maximum flow is also discussed. The algorithm...
The linear complexity of a graph.
The maximum number of edges in a three-dimensional grid-drawing.
The minimal density of a letter in an infinite ternary square-free word is 883/3215.
The minimal density of a letter in an infinite ternary square-free word is .
The monadic second-order logic of graphs III : tree-decompositions, minors and complexity issues
The number of binary rotation words
We consider binary rotation words generated by partitions of the unit circle to two intervals and give a precise formula for the number of such words of length n. We also give the precise asymptotics for it, which happens to be Θ(n4). The result continues the line initiated by the formula for the number of all Sturmian words obtained by Lipatov [Problemy Kibernet. 39 (1982) 67–84], then independently by Mignosi [Theoret. Comput. Sci. 82 (1991) 71–84], and others.
The number of positions starting a square in binary words.
The number of ternary words avoiding abelian cubes grows exponentially.
The reduction of binary trees by means of an input-restricted deque
The rupture degree and gear graphs.
The second-order monadic theory of the free inverse monoid is undecidable. (La théorie monadique du second ordre du monoïde inversif libre est indécidable.)
The stack-size of combinatorial tries revisited.
The star clustering algorithm for static and dynamic information organization.
The subword complexity of a two-parameter family of sequences.
The sum-product algorithm: algebraic independence and computational aspects
The sum-product algorithm is a well-known procedure for marginalizing an “acyclic” product function whose range is the ground set of a commutative semiring. The algorithm is general enough to include as special cases several classical algorithms developed in information theory and probability theory. We present four results. First, using the sum-product algorithm we show that the variable sets involved in an acyclic factorization satisfy a relation that is a natural generalization of probability-theoretic...
The theorem of Fine and Wilf for relational periods
We consider relational periods, where the relation is a compatibility relation on words induced by a relation on letters. We prove a variant of the theorem of Fine and Wilf for a (pure) period and a relational period.
The theorem of Fine and Wilf for relational periods
We consider relational periods, where the relation is a compatibility relation on words induced by a relation on letters. We prove a variant of the theorem of Fine and Wilf for a (pure) period and a relational period.