In this paper we study the problem of sorting under forbidden comparisons where some pairs of elements may not be compared (forbidden pairs). Along with the set of elements V the input to our problem is a graph G(V, E), whose edges represents the pairs that we can compare in constant time. Given a graph with n vertices and m =(n2) - q edges we propose the first non-trivial deterministic algorithm which makes O((q + n) log n) comparisons with a total complexity of O(n2 + qω/2), where ω is the exponent in the complexity of matrix multiplication. We also propose a simple randomized algorithm for the problem which makes Õ(n2/√q + n+n√q) probes with high probability. When the input graph is random we show that Õ(min (n3/2, pn2)) probes suffice, where p is the edge probability.
A. Banerjee and D. Richards, "Sorting under Forbidden Comparisons," Leibniz International Proceedings in Informatics, LIPIcs, vol. 53, pp. 22.1-22.13, Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, Jun 2016.
The definitive version is available at https://doi.org/10.4230/LIPIcs.SWAT.2016.22
15th Scandinavian Symposium and Workshops on Algorithm Theory, SWAT 2016 (2016: Jun. 22-24, Reykjavik, Iceland)
Keywords and Phrases
Complexity; Random Graphs; Sorting
International Standard Book Number (ISBN)
International Standard Serial Number (ISSN)
Article - Conference proceedings
© 2016 The Authors, All rights reserved.
Creative Commons Licensing
This work is licensed under a Creative Commons Attribution 4.0 License.
24 Jun 2016