Techniques for the refinement of orthogonal graph drawings.
The conjugacy map over a Sturmian word.
The problem, generalized Pascal triangles and cellular automata
The box parameter for words and permutations
The box parameter for words counts how often two letters w j and w k define a “box” such that all the letters w j+1; ..., w k−1 fall into that box. It is related to the visibility parameter and other parameters on words. Three models are considered: Words over a finite alphabet, permutations, and words with letters following a geometric distribution. A typical result is: The average box parameter for words over an M letter alphabet is asymptotically given by 2n − 2n H M/M, for fixed M and n → ∞.
The code problem for directed figures
We consider directed figures defined as labelled polyominoes with designated start and end points, with two types of catenation operations. We are especially interested in codicity verification for sets of figures, and we show that depending on the catenation type the question whether a given set of directed figures is a code is decidable or not. In the former case we give a constructive proof which leads to a straightforward algorithm.
The code problem for directed figures
We consider directed figures defined as labelled polyominoes with designated start and end points, with two types of catenation operations. We are especially interested in codicity verification for sets of figures, and we show that depending on the catenation type the question whether a given set of directed figures is a code is decidable or not. In the former case we give a constructive proof which leads to a straightforward algorithm.
The completely distributive lattice of machine invariant sets of infinite words
We investigate the lattice of machine invariant classes. This is an infinite completely distributive lattice but it is not a Boolean lattice. The length and width of it is c. We show the subword complexity and the growth function create machine invariant classes.
The critical exponent of the Arshon words
Generalizing the results of Thue (for n = 2) [Norske Vid. Selsk. Skr. Mat. Nat. Kl. 1 (1912) 1–67] and of Klepinin and Sukhanov (for n = 3) [Discrete Appl. Math. 114 (2001) 155–169], we prove that for all n ≥ 2, the critical exponent of the Arshon word of order n is given by (3n–2)/(2n–2), and this exponent is attained at position 1.
The crossing number of a projective graph is quadratic in the face-width.
The cycles of the multiway perfect shuffle permutation.
The Fan-Raspaud conjecture: A randomized algorithmic approach and application to the pair assignment problem in cubic networks
It was conjectured by Fan and Raspaud (1994) that every bridgeless cubic graph contains three perfect matchings such that every edge belongs to at most two of them. We show a randomized algorithmic way of finding Fan-Raspaud colorings of a given cubic graph and, analyzing the computer results, we try to find and describe the Fan-Raspaud colorings for some selected classes of cubic graphs. The presented algorithms can then be applied to the pair assignment problem in cubic computer networks. Another...
The greedy algorithm as a combinatorial principle.
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