The solution space of sorting with recurring comparison faults

DOI10.1007/S00224-017-9807-4MaRDI QIDQ726101zbMATH OpenOpenAlexWikidataFDO

Authors Peter Damaschke

Publication date 3 August 2018

Published in Theory of Computing Systems (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.1007/s00224-017-9807-4

zbMATH Keywords

enumerationfixed-parameter tractabilitysortingfeedback arc setfaulty input

Mathematics Subject Classification ID

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

Recommendations

• The solution space of sorting with recurring comparison faults
• Recurring comparison faults: sorting and finding the minimum
• scientific article; zbMATH DE number 2089999
• Braking the (n^ 2 n) barrier for sorting with faults
• scientific article; zbMATH DE number 871920

Cites work

• Algorithmic Aspects of Vertex Elimination on Graphs
• Fault-tolerant search algorithms. Reliable computation with unreliable information
• Kernels for feedback arc set in tournaments
• Noisy sorting without resampling
• On the complexity of partial order properties
• Optimal Resilient Sorting and Searching in the Presence of Memory Faults
• Parameterized algorithms for feedback set problems and their duals in tournaments
• Recurring comparison faults: sorting and finding the minimum
• Structural filtering: a paradigm for efficient and exact geometric programs
• Subexponential parameterized algorithm for computing the cutwidth of a semi-complete digraph
• The art of computer programming. Volume 4A. Combinatorial algorithms. Part 1.

Cited in

(5)

• Recurring comparison faults: sorting and finding the minimum
• Sorting and searching in the presence of memory faults (without redundancy)
• scientific article; zbMATH DE number 2089999 (Why is no real title available?)
• Sorting with Recurrent Comparison Errors
• The solution space of sorting with recurring comparison faults

This page was built for publication: The solution space of sorting with recurring comparison faults

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q726101)