The Solution Space of Sorting with Recurring Comparison Faults

DOI10.1007/978-3-319-44543-4_31zbMath1391.68024OpenAlexW2512134815MaRDI QIDQ2819522

Peter Damaschke

Publication date: 29 September 2016

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://research.chalmers.se/en/publication/b0dcb816-6fa2-408b-b0ec-9f187b3cad21

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Searching and sorting (68P10) Graph theory (including graph drawing) in computer science (68R10) Directed graphs (digraphs), tournaments (05C20)

Related Items (5)

Optimal Dislocation with Persistent Errors in Subquadratic Time ⋮ Optimal dislocation with persistent errors in subquadratic time ⋮ Unnamed Item ⋮ Longest increasing subsequence under persistent comparison errors ⋮ Sorting with Recurrent Comparison Errors

Cites Work

• Unnamed Item
• Fault-tolerant search algorithms. Reliable computation with unreliable information
• Kernels for feedback arc set in tournaments
• Parameterized algorithms for feedback set problems and their duals in tournaments
• On the complexity of partial order properties
• Subexponential Parameterized Algorithm for Computing the Cutwidth of a Semi-complete Digraph
• Recurring Comparison Faults: Sorting and Finding the Minimum
• Optimal Resilient Sorting and Searching in the Presence of Memory Faults
• Algorithmic Aspects of Vertex Elimination on Graphs

This page was built for publication: The Solution Space of Sorting with Recurring Comparison Faults