Traversing directed Eulerian mazes.
Treewidth and minimum fill-in on -trapezoid graphs.
Triangle-free planar graphs and segment intersection graphs.
Two linear time algorithms for MST on minor closed graph classes
This article presents two simple deterministic algorithms for finding the Minimum Spanning Tree in time for any non-trivial class of graphs closed on graph minors. This applies in particular to planar graphs and graphs of bounded genus. Both algorithms run on a pointer machine and they require no a priori knowledge of the structure of the class except for its density. Edge weights are only compared.
Two sided Sand Piles Model and unimodal sequences
We introduce natural generalizations of two well-known dynamical systems, the Sand Piles Model and the Brylawski's model. We describe their order structure, their reachable configuration's characterization, their fixed points and their maximal and minimal length's chains. Finally, we present an induced model generating the set of unimodal sequences which amongst other corollaries, implies that this set is equipped with a lattice structure.
Two-variable word equations
Two-variable word equations
We consider languages expressed by word equations in two variables and give a complete characterization for their complexity functions, that is, the functions that give the number of words of the same length. Specifically, we prove that there are only five types of complexities: constant, linear, exponential, and two in between constant and linear. For the latter two, we give precise characterizations in terms of the number of solutions of Diophantine equations of certain types. In particular,...