2-Stack Sorting is polynomial

Pierrot, Adeline; Rossin, Dominique

doi:10.4230/LIPIcs.STACS.2014.614

Document

2-Stack Sorting is polynomial

Authors Adeline Pierrot, Dominique Rossin

Part of: Volume: 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014)
Part of: Series: Leibniz International Proceedings in Informatics (LIPIcs)
Part of: Conference: Symposium on Theoretical Aspects of Computer Science (STACS)
License: Creative Commons Attribution 3.0 Unported license
Publication Date: 2014-03-05

PDF

File

PDF

LIPIcs.STACS.2014.614.pdf

Filesize: 0.68 MB
13 pages

Document Identifiers

DOI: 10.4230/LIPIcs.STACS.2014.614
URN: urn:nbn:de:0030-drops-44927

Subject Classification

Keywords

permutation
stack
sort
NP-complete

Metrics

Access Statistics
Total Accesses (updated on a weekly basis)

0

PDF Downloads

0

Metadata Views

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.

Cite As Get 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

Author Details

Adeline Pierrot

Dominique Rossin

Questions / Remarks / Feedback

Feedback for Dagstuhl Publishing

Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail