Fast and longest rollercoasters

DOI10.1007/S00453-021-00908-6MaRDI QIDQ2118392zbMATH OpenOpenAlexFDO

Authors Florin Manea, Radosław Serafin, Paweł Gawrychowski

Publication date 22 March 2022

Published in Algorithmica (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.1007/s00453-021-00908-6

zbMATH Keywords

alternating runsefficient algorithmspatterns in permutationsrollercoasterssequences

Mathematics Subject Classification ID

Graph theory (05Cxx) Algorithms in computer science (68Wxx)

Recommendations

• Fast and longest rollercoasters
• Rollercoasters: Long Sequences without Short Runs
• Rollercoasters and caterpillars
• Some properties of roller coaster permutations
• The Longest Almost-Increasing Subsequence

Cites work

• A decomposition theorem for partially ordered sets
• A fast algorithm for computing longest common subsequences
• A Functional Approach to Data Structures and Its Use in Multidimensional Searching
• Applications of generalized matrix searching to geometric algorithms
• Enumerating longest increasing subsequences and patience sorting
• Fast computation of a longest increasing subsequence and application
• Fast distance multiplication of unit-Monge matrices
• Geometric applications of a matrix-searching algorithm
• scientific article; zbMATH DE number 5729471 (Why is no real title available?)
• scientific article; zbMATH DE number 795114 (Why is no real title available?)
• Improved bounds for drawing trees on fixed points with L-shaped edges
• Longest Increasing and Decreasing Subsequences
• Longest increasing subsequences: from patience sorting to the Baik-Deift-Johansson theorem
• On computing the length of longest increasing subsequences
• Patterns in permutations and words.
• Rollercoasters and caterpillars
• Rollercoasters: Long Sequences without Short Runs
• The communication and streaming complexity of computing the longest common and increasing subsequences
• The surprising mathematics of longest increasing subsequences

Cited in

(8)

• Longest common rollercoasters
• Computing longest (common) Lyndon subsequences
• Fast and longest rollercoasters
• Rollercoasters: Long Sequences without Short Runs
• Longest bordered and periodic subsequences
• Subsequences in bounded ranges: matching and analysis problems
• Approximate Cartesian tree pattern matching
• Approximate Cartesian tree pattern matching

This page was built for publication: Fast and longest rollercoasters

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2118392)