Scheduled hot-potato routing.
Scheduling partial round Robin tournaments subject to home away pattern sets.
Scheduling trajectories on a planar surface with moving obstacles.
Self-diclique circulant digraphs
We study a particular digraph dynamical system, the so called digraph diclique operator. Dicliques have frequently appeared in the literature the last years in connection with the construction and analysis of different types of networks, for instance biochemical, neural, ecological, sociological and computer networks among others. Let be a reflexive digraph (or network). Consider and (not necessarily disjoint) nonempty subsets of vertices (or nodes) of . A disimplex of is the subdigraph...
Semidefinite programming and combinatorial optimization.
Sequences of low arithmetical complexity
Arithmetical complexity of a sequence is the number of words of length n that can be extracted from it according to arithmetic progressions. We study uniformly recurrent words of low arithmetical complexity and describe the family of such words having lowest complexity.
Seriation with applications in philology
Several methods of the reduction of computational complexity.
Signed Chip Firing Games and symmetric Sandpile Models on the cycles
We investigate the Sandpile Model and Chip Firing Game and an extension of these models on cycle graphs. The extended model consists of allowing a negative number of chips at each vertex. We give the characterization of reachable configurations and of fixed points of each model. At the end, we give explicit formula for the number of their fixed points.
Simple and efficient bilayer cross counting.
Simultaneous embedding of planar graphs with few bends.
Simultaneous graph drawing: layout algorithms and visualization schemes.
Skip trees, an alternative data structure to skip lists in a concurrent approach
Small maximal independent sets and faster exact graph coloring.
Small stretch spanners on dynamic graphs.
Smooth and sharp thresholds for random -XOR-CNF satisfiability
The aim of this paper is to study the threshold behavior for the satisfiability property of a random -XOR-CNF formula or equivalently for the consistency of a random Boolean linear system with variables per equation. For we show the existence of a sharp threshold for the satisfiability of a random -XOR-CNF formula, whereas there are smooth thresholds for and .
Smooth and sharp thresholds for random {k}-XOR-CNF satisfiability
The aim of this paper is to study the threshold behavior for the satisfiability property of a random k-XOR-CNF formula or equivalently for the consistency of a random Boolean linear system with k variables per equation. For k ≥ 3 we show the existence of a sharp threshold for the satisfiability of a random k-XOR-CNF formula, whereas there are smooth thresholds for k=1 and k=2.
Some Algebraic Properties of Machine Poset of Infinite Words
The complexity of infinite words is considered from the point of view of a transformation with a Mealy machine that is the simplest model of a finite automaton transducer. We are mostly interested in algebraic properties of the underlying partially ordered set. Results considered with the existence of supremum, infimum, antichains, chains and density aspects are investigated.
Some algorithms on the star operation applied to finite languages.
Some algorithms to compute the conjugates of episturmian morphisms
Episturmian morphisms generalize sturmian morphisms. They are defined as compositions of exchange morphisms and two particular morphisms , and . Epistandard morphisms are the morphisms obtained without considering . In [14], a general study of these morphims and of conjugacy of morphisms is given. Here, given a decomposition of an Episturmian morphism over exchange morphisms and , we consider two problems: how to compute a decomposition of one conjugate of ; how to compute a list of decompositions...