Asset Details
Do you wish to reserve the book?
Deciding Foot-sortability and Minimal 2-bounded Non-foot-sortable Sock Orderings
Hey, we have placed the reservation for you!
By the way, why not check out events that you can attend while you pick your title.
Oops! Something went wrong.
Looks like we were not able to place the reservation. Kindly try again later.
Are you sure you want to remove the book from the shelf?
Deciding Foot-sortability and Minimal 2-bounded Non-foot-sortable Sock Orderings
Do you wish to request the book?
Deciding Foot-sortability and Minimal 2-bounded Non-foot-sortable Sock Orderings
Please be aware that the book you have requested cannot be checked out. If you would like to checkout this book, you can reserve another copy
We have requested the book for you!
Your request is successful and it will be processed during the Library working hours. Please check the status of your request in My Requests.
Oops! Something went wrong.
Looks like we were not able to place your request. Kindly try again later.
Paper
Deciding Foot-sortability and Minimal 2-bounded Non-foot-sortable Sock Orderings
2023
Overview
A sock ordering is a sequence of socks with different colors. A sock ordering is foot-sortable if the sequence of socks can be sorted by a stack so that socks with the same color form a contiguous block. The problem of deciding whether a given sock ordering is foot-sortable was first considered by Defant and Kravitz, who resolved the case for alignment-free 2-uniform sock orderings. In this paper, we resolve the problem in a more general setting, where each color appears in the sock ordering at most twice. A key component of the argument is a fast algorithm that determines the foot-sortability of a sock ordering of length \\(N\\) in time \\(O(N\\log N)\\), which is also an interesting result on its own.
Publisher
Cornell University Library, arXiv.org
Subject
