DROPS

Document

DOI: 10.4230/LIPIcs.SWAT.2016.22

Sorting Under Forbidden Comparisons

Authors: Indranil Banerjee and Dana Richards

Published in: LIPIcs, Volume 53, 15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016)

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

Cite as

Indranil Banerjee and Dana Richards. Sorting Under Forbidden Comparisons. In 15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 53, pp. 22:1-22:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{banerjee_et_al:LIPIcs.SWAT.2016.22,
  author =	{Banerjee, Indranil and Richards, Dana},
  title =	{{Sorting Under Forbidden Comparisons}},
  booktitle =	{15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016)},
  pages =	{22:1--22:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-011-8},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{53},
  editor =	{Pagh, Rasmus},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2016.22},
  URN =		{urn:nbn:de:0030-drops-60448},
  doi =		{10.4230/LIPIcs.SWAT.2016.22},
  annote =	{Keywords: Sorting, Random Graphs, Complexity}
}

Search Results

Documents authored by Richards, Dana

Sorting Under Forbidden Comparisons

Abstract

Cite as

Thanks for your feedback!

Could not send message