Sorting Permutations with Fixed Pinnacle Set
January 23, 2020 Β· Declared Dead Β· π Electronic Journal of Combinatorics
"No code URL or promise found in abstract"
Evidence collected by the PWNC Scanner
Authors
Irena Rusu
arXiv ID
2001.08417
Category
cs.DS: Data Structures & Algorithms
Cross-listed
math.CO
Citations
6
Venue
Electronic Journal of Combinatorics
Last Checked
4 months ago
Abstract
We give a positive answer to a question raised by Davis et al. ({\em Discrete Mathematics} 341, 2018), concerning permutations with the same pinnacle set. Given $Ο\in S_n$, a {\em pinnacle} of $Ο$ is an element $Ο_i$ ($i\neq 1,n$) such that $Ο_{i-1}<Ο_i>Ο_{i+1}$. The question is: given $Ο,Ο'\in S_n$ with the same pinnacle set $S$, is there a sequence of operations that transforms $Ο$ into $Ο'$ such that all the intermediate permutations have pinnacle set $S$? We introduce {\em balanced reversals}, defined as reversals that do not modify the pinnacle set of the permutation to which they are applied. Then we show that $Ο$ may be sorted by balanced reversals (i.e. transformed into a standard permutation $\Id_S$), implying that $Ο$ may be transformed into $Ο'$ using at most $4n-2\min\{p,3\}$ balanced reversals, where $p=|S|\geq 1$. In case $p=0$, at most $2n-1$ balanced reversals are needed.
Community Contributions
Found the code? Know the venue? Think something is wrong? Let us know!
π Similar Papers
In the same crypt β Data Structures & Algorithms
π
π
The Cartographer
R.I.P.
π»
Ghosted
Route Planning in Transportation Networks
R.I.P.
π»
Ghosted
Near-linear time approximation algorithms for optimal transport via Sinkhorn iteration
R.I.P.
π»
Ghosted
Hierarchical Clustering: Objective Functions and Algorithms
R.I.P.
π»
Ghosted
Graph Isomorphism in Quasipolynomial Time
π
π
The Cartographer
Simulation optimization: A review of algorithms and applications
Died the same way β π» Ghosted
R.I.P.
π»
Ghosted
Federated Learning: Strategies for Improving Communication Efficiency
R.I.P.
π»
Ghosted
In-Datacenter Performance Analysis of a Tensor Processing Unit
R.I.P.
π»
Ghosted
Deep Convolutional Neural Networks for Computer-Aided Detection: CNN Architectures, Dataset Characteristics and Transfer Learning
R.I.P.
π»
Ghosted