Displaying similar documents to “Non-Trapping sets and Huygens Principle”

Towards parametrizing word equations

H. Abdulrab, P. Goralčík, G. S. Makanin (2010)

RAIRO - Theoretical Informatics and Applications

Similarity:

Classically, in order to resolve an equation ≈ over a free monoid *, we reduce it by a suitable family of substitutions to a family of equations ≈ , f , each involving less variables than ≈ , and then combine solutions of ≈ into solutions of ≈ . The problem is to get in a handy form. The method we propose consists in parametrizing the path traces in the so called associated to ≈ . We carry out such a parametrization in the case the prime equations in the graph involve at...

On the power of randomization for job shop scheduling with -units length tasks

Tobias Mömke (2008)

RAIRO - Theoretical Informatics and Applications

Similarity:

In the job shop scheduling problem -- , there are machines and each machine has an integer processing time of at most time units. Each job consists of a permutation of tasks corresponding to all machines and thus all jobs have an identical dilation . The contribution of this paper are the following results; (i) for d = o ( D ) jobs and every fixed , the makespan of an optimal schedule is at most , which extends the result of [3] for ; (ii) a randomized on-line approximation...