License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.SWAT.2016.22
URN: urn:nbn:de:0030-drops-60448
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2016/6044/
Go to the corresponding LIPIcs Volume Portal

Banerjee, Indranil ; Richards, Dana

Sorting Under Forbidden Comparisons

pdf-format:
LIPIcs-SWAT-2016-22.pdf (0.6 MB)

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.

BibTeX - Entry

@InProceedings{banerjee_et_al:LIPIcs:2016:6044,
  author =	{Indranil Banerjee and Dana Richards},
  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 =	{Rasmus Pagh},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2016/6044},
  URN =		{urn:nbn:de:0030-drops-60448},
  doi =		{10.4230/LIPIcs.SWAT.2016.22},
  annote =	{Keywords: Sorting, Random Graphs, Complexity}
}

Keywords: Sorting, Random Graphs, Complexity
Collection: 15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016)
Issue Date: 2016
Date of publication: 22.06.2016

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI