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 =(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.

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

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

Publication Date

24 Jun 2016

Download

Full Text Link

Share

 
COinS