## Contributed Session Tue.1.H 3013

#### Tuesday, 10:30 - 12:00 h, Room: H 3013

**Cluster 2: Combinatorial optimization** [...]

### Trees and words

**Chair: Winfried HochstÃ¤ttler**

**Tuesday, 10:30 - 10:55 h, Room: H 3013, Talk 1**

**Winfried HochstÃ¤ttler**

Some heuristics for the binary paint shop problem and their expected number of colour changes

**Coauthor: Stephan D. Andres**

**Abstract:**

In the binary paint shop problem we are given a word on *n*

characters of length *2n* where every character occurs exactly

twice. The objective is to color the letters of the word in two

colors, such that each character receives both colors and the

number of color changes of consecutive letters is minimized. Amini

et. al proved that the expected number of color changes of the heuristic

greedy coloring is at most *2n/3*. They also conjectured

that the true value is *n/2*. We verify their conjecture

and, furthermore, compute an expected number of *2n/3*

colour changes for a heuristic, named *red first*, which behaves

well on some worst case examples for the greedy algorithm.

From our proof method, finally, we derive a new recursive greedy heuristic which achieves an average number of *2n/5* color changes.

**Tuesday, 11:00 - 11:25 h, Room: H 3013, Talk 2**

**Marcin Krzywkowski**

An algorithm listing all minimal dominating sets of a tree

**Abstract:**

We provide an algorithm listing all minimal dominating sets of a tree of order *n* in time **O**(1.4656^{n}). This leads to that every tree has at most *1.4656*^{n} minimal dominating sets. We also give an infinite family of trees of odd and even order for which the number of minimal dominating sets exceeds *1.4167*^{n}, thus exceeding *2*^{n/2}. This establishes a lower bound on the running time of an algorithm listing all minimal dominating sets of a given tree.

**Tuesday, 11:30 - 11:55 h, Room: H 3013, Talk 3**

**Yasuko Matsui**

An enumeration algorithm for the optimal cost vertex-colorings for trees

**Coauthors: Kento Kizaka, Hiroki Yoshida**

**Abstract:**

The cost vertex-coloring problem is to find a vertex-coloring of a graph such that the total costs of vertices is as small as possible. In 1997, Kroon et al. gave the problem can be solved in linear time for trees. In this talk, we first propose an enumeration algorithm for the optimal cost

vertex-colorings for trees, if there exists. Our algorithm has a polynomial-time delay property and requires polynomial space.