Algorithms for compact letter displays: Comparison and evaluation
- 作者：Jens Gramm ; Jiong Guo ; Falk Hü ; ffner ; Rolf Niedermeier ; Hans-Peter Piepho ; Ramona Schmid
- 关键词：Multiple pairwise comparison ; Line display ; NP-hard problem ; Graph problem ; Clique cover ; Efficient algorithm
- 刊名：Computational Statistics and Data Analysis
- 出版年：2007
- 期刊代码：19_01679473
- 类别：cp
- 出版时间：15 October 2007
- 卷：52
- 期：2
- 页码：725-736
- 文件大小：249 K
摘要
Multiple pairwise comparisons are one of the most frequent tasks in applied statistics. In this context, letter displays may be used for a compact presentation of results of multiple comparisons. A heuristic previously proposed for this task is compared with two new algorithmic approaches. The latter rely on the equivalence of computing compact letter displays to computing clique covers in graphs, a problem that is well-studied in theoretical computer science. A thorough discussion of the three approaches aims to give a comparison of the algorithms’ advantages and disadvantages. The three algorithms are compared in a series of experiments on simulated and real data, e.g., using data from wheat and triticale yield trials.