Sorting under Forbidden Comparisons

Author

Avah Banerjee, Missouri University of Science and TechnologyFollow
Dana Richards

Abstract

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 =(ⁿ₂) - q edges we propose the first non-trivial deterministic algorithm which makes O((q + n) log n) comparisons with a total complexity of O(n² + q^ω/2), where ω is the exponent in the complexity of matrix multiplication. We also propose a simple randomized algorithm for the problem which makes Õ(n²/√q + n+n√q) probes with high probability. When the input graph is random we show that Õ(min (n^3/2, pn²)) probes suffice, where p is the edge probability.

Recommended Citation

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

Meeting Name

15th Scandinavian Symposium and Workshops on Algorithm Theory, SWAT 2016 (2016: Jun. 22-24, Reykjavik, Iceland)

Department(s)

Computer Science

Comments

Published as Indranil Banerjee.

Keywords and Phrases

Complexity; Random Graphs; Sorting

International Standard Book Number (ISBN)

978-395977011-8

International Standard Serial Number (ISSN)

1868-8969

Document Type

Article - Conference proceedings

Document Version

Final Version

File Type

text

Language(s)

English

Rights

© 2016 The Authors, All rights reserved.

Creative Commons Licensing

This work is licensed under a Creative Commons Attribution 4.0 License.

Publication Date

24 Jun 2016