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.4656n). This leads to that every tree has at most 1.4656n 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.4167n, thus exceeding 2n/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.

 

  payday advance . In this section we give only a brief summary recommendation for admission of Levitra. Full information can be found in the instructions for receiving medications with vardenafil.