Greedy colorings of words

详细信息	查看全文 | 推荐本文 |

• 作者：Dieter Rautenbach^a ; ^{dieter.rautenbach@uni-ulm.de} ; ^{dieter.rautenbach@gmx.de} ; Zoltá ; n Szigeti^b ; ^{zoltan.szigeti@g-scop.inpg.fr}
• 关键词：Binary paint shop problem ; Greedy algorithm ; Evenly laminar hypergraph ; Odd transversal
• 刊名：Discrete Applied Mathematics
• 出版年：2012
• 期刊代码：46_0166218x
• 类别：cp
• 出版时间：August, 2012
• 卷：160
• 期：12
• 页码：1872-1874
• 文件大小：183 K

摘要

In the Binary Paint Shop Problem proposed by Epping et聽al. (2004) one has to find a -coloring of the letters of a word in which every letter from some alphabet appears twice, such that the two occurrences of each letter are colored differently and the total number of color changes is minimized. Meunier and Seb艖 (2009) and Amini et聽al. (2010) gave sufficient conditions for the optimality of a natural greedy algorithm for this problem. Our result is a best possible generalization of their results. We prove that the greedy algorithm optimally colors every suitable subword of a given instance word if and only if contains none of the three words , , and as a subword. Furthermore, we relate this to the fact that every member of a family of hypergraphs associated with is evenly laminar.