2026-07-26T04:14:55Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:6044 2024-03-06T10:37:31Z ddc:004 open_access

Sorting Under Forbidden Comparisons Banerjee, Indranil Richards, Dana Sorting Random Graphs Complexity 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 = binom(n)(2) - 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^2 + q^(omega/2)), where omega is the exponent in the complexity of matrix multiplication. We also propose a simple randomized algorithm for the problem which makes widetilde O(n^2/sqrt(q+n) + nsqrt(q)) probes with high probability. When the input graph is random we show that widetilde O(min(n^(3/2), pn^2)) probes suffice, where p is the edge probability. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Indranil Banerjee and Dana Richards 2016 Is Part Of LIPIcs, Volume 53, 15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SWAT.2016.22 urn:nbn:de:0030-drops-60448 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2016.22 eng https://creativecommons.org/licenses/by/3.0/legalcode