Rollercoasters: Long Sequences without Short Runs

DOI10.1137/18M1192226zbMath1419.05005MaRDI QIDQ5232132

Anna Lubiw, Robert Cummings, Dirk Nowotka, Ahmad Biniaz, Florin Manea, Jeffrey O. Shallit, Therese C. Biedl

Publication date: 29 August 2019

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

zbMATH Keywords

sequencesalternating runscaterpillarspatterns in permutations

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Permutations, words, matrices (05A05) Enumeration in graph theory (05C30) Number-theoretic algorithms; complexity (11Y16) General theory of distance geometry (51K05)

Related Items (6)

Longest common rollercoasters ⋮ Computing longest (common) Lyndon subsequences ⋮ Computing longest Lyndon subsequences and longest common Lyndon subsequences ⋮ Longest bordered and periodic subsequences ⋮ Subsequences in bounded ranges: matching and analysis problems ⋮ Fast and longest rollercoasters

Uses Software

• OEIS

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Patterns in permutations and words.
• Counting and generating permutations in regular classes
• On computing the length of longest increasing subsequences
• Preserving order in a forest in less than logarithmic time and linear space
• On L-shaped point set embeddings of trees: first non-embeddable examples
• Descent pattern avoidance
• Fast computation of a longest increasing subsequence and application
• Orthogeodesic point-set embedding of trees
• The Surprising Mathematics of Longest Increasing Subsequences
• Improved Bounds for Drawing Trees on Fixed Points with L-Shaped Edges

This page was built for publication: Rollercoasters: Long Sequences without Short Runs