2-Stack Sorting is polynomial

Authors Adeline Pierrot, Dominique Rossin



PDF
Thumbnail PDF

File

LIPIcs.STACS.2014.614.pdf
  • Filesize: 0.68 MB
  • 13 pages

Document Identifiers

Author Details

Adeline Pierrot
Dominique Rossin

Cite AsGet BibTex

Adeline Pierrot and Dominique Rossin. 2-Stack Sorting is polynomial. In 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 25, pp. 614-626, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)
https://doi.org/10.4230/LIPIcs.STACS.2014.614

Abstract

This article deals with deciding whether a permutation is sortable with two stacks in series. Whether this decision problem lies in P or is NP-complete is a longstanding open problem since the introduction of serial compositions of stacks by Knuth in The Art of Computer Programming in 1973. We hereby prove that this decision problem lies in P by giving a polynomial algorithm to solve it. This algorithm uses the concept of pushall sorting, which was previously defined and studied by the authors.
Keywords
  • permutation
  • stack
  • sort
  • NP-complete

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
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