CPL - Chalmers Publication Library
| Utbildning | Forskning | Styrkeområden | Om Chalmers | In English In English Ej inloggad.

The solution space of sorting with recurring comparison faults

Peter Damaschke (Institutionen för data- och informationsteknik, Datavetenskap, Algoritmer (Chalmers))
27th International Workshop on Combinatorial Algorithms IWOCA 2016, Lecture Notes in Computer Science Vol. 9843 (2016), p. 397-408 .
[Konferensbidrag, refereegranskat]

Suppose that n elements shall be sorted by comparisons, but an unknown subset of at most k pairs systematically returns false comparison results. Using a known connection with feedback arc sets in tournaments (FAST), we characterize the solution space of sorting with recurring comparison faults by a FAST enumeration, which represents all information about the order that can be obtained by doing all possible comparisons. An optimal parameterized enumeration algorithm for FAST also works for the more general chordal graphs, and this fact contributes to the efficiency of our representation. Then, we compute the solution space more efficiently, by fault-tolerant versions of Treesort and Quicksort. For rare faults the complexity is close to optimal.



Denna post skapades 2016-08-29.
CPL Pubid: 240881