Erdös-Szekeres Partitioning Problem

2020/11/21 by Michael Mitzenmacher, Mitzenmacher, Michael, Saeed Seddighin +1
Computer Science · Engineering · #Advanced Graph Theory Research #semigroups and automata theory #graph theory and CDMA systems

paper · pdf · doi:10.48550/arxiv.2011.10870

Abstract

In this note, we present a substantial improvement on the computational complexity of the Erdös-Szekeres partitioning problem and review recent works on dynamic \textsfLIS.

Related

• Dynamic Longest Increasing Subsequence and the Erdös-Szekeres Partitioning Problem
• Fully Dynamic Approximation of LIS in Polylogarithmic Time
• On Erdös--Szekeres problem and related problems
• Generating All Partitions: A Comparison Of Two Encodings
• Hypergraph partitions