1 Search Results for "Robertson, Matthew"


Document
Raising Permutations to Powers in Place

Authors: Hicham El-Zein, J. Ian Munro, and Matthew Robertson

Published in: LIPIcs, Volume 64, 27th International Symposium on Algorithms and Computation (ISAAC 2016)


Abstract
Given a permutation of n elements, stored as an array, we address the problem of replacing the permutation by its kth power. We aim to perform this operation quickly using o(n) bits of extra storage. To this end, we first present an algorithm for inverting permutations that uses O(lg^2 n) additional bits and runs in O(n lg n) worst case time. This result is then generalized to the situation in which the permutation is to be replaced by its kth power. An algorithm whose worst case running time is O(n lg n) and uses O(lg^2 n + min{k lg n, n^{3/4 + epsilon}}) additional bits is presented.

Cite as

Hicham El-Zein, J. Ian Munro, and Matthew Robertson. Raising Permutations to Powers in Place. In 27th International Symposium on Algorithms and Computation (ISAAC 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 64, pp. 29:1-29:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)


Copy BibTex To Clipboard

@InProceedings{elzein_et_al:LIPIcs.ISAAC.2016.29,
  author =	{El-Zein, Hicham and Munro, J. Ian and Robertson, Matthew},
  title =	{{Raising Permutations to Powers in Place}},
  booktitle =	{27th International Symposium on Algorithms and Computation (ISAAC 2016)},
  pages =	{29:1--29:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-026-2},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{64},
  editor =	{Hong, Seok-Hee},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2016.29},
  URN =		{urn:nbn:de:0030-drops-67992},
  doi =		{10.4230/LIPIcs.ISAAC.2016.29},
  annote =	{Keywords: Algorithms, Combinatorics, Inplace, Permutations, Powers}
}
  • Refine by Author
  • 1 El-Zein, Hicham
  • 1 Munro, J. Ian
  • 1 Robertson, Matthew

  • Refine by Classification

  • Refine by Keyword
  • 1 Algorithms
  • 1 Combinatorics
  • 1 Inplace
  • 1 Permutations
  • 1 Powers

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2016

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail