Improved bounds and new techniques for Davenport--Schinzel sequences and their generalizations
From MaRDI portal
Publication:3578194
DOI10.1145/1706591.1706597zbMath1327.68183arXiv0807.0484OpenAlexW1768195728MaRDI QIDQ3578194
Publication date: 14 July 2010
Published in: Journal of the ACM (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/0807.0484
Computational aspects related to convexity (52B55) Combinatorics on words (68R15) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)
Related Items (24)
Almost all permutation matrices have bounded saturation functions ⋮ Three Generalizations of Davenport--Schinzel Sequences ⋮ A generalization of the K\H{o}v\'{a}ri-S\'{o}s-Tur\'{a}n theorem ⋮ Improved enumeration of simple topological graphs ⋮ Constructing sparse Davenport-Schinzel sequences ⋮ k-Quasi-Planar Graphs ⋮ Bounding sequence extremal functions with formations ⋮ Forbidden formations in multidimensional 0-1 matrices ⋮ Bounds on parameters of minimally nonlinear patterns ⋮ Degrees of nonlinearity in forbidden 0-1 matrix problems ⋮ Querying two boundary points for shortest paths in a polygonal domain ⋮ New bounds on the maximum number of edges in \(k\)-quasi-planar graphs ⋮ Tight bounds on the maximum size of a set of permutations with bounded VC-dimension ⋮ Unnamed Item ⋮ On the zone of a circle in an arrangement of lines ⋮ On the zone of a circle in an arrangement of lines ⋮ Finding best swap edges minimizing the routing cost of a spanning tree ⋮ Disjoint edges in topological graphs and the tangled-thrackle conjecture ⋮ Lower bounds on Davenport-Schinzel sequences via rectangular Zarankiewicz matrices ⋮ Lower bounds for weak epsilon-nets and stair-convexity ⋮ Generalized Davenport-Schinzel sequences and their 0-1 matrix counterparts ⋮ Linear bounds on matrix extremal functions using visibility hypergraphs ⋮ A relationship between generalized Davenport-Schinzel sequences and interval chains ⋮ Unnamed Item
This page was built for publication: Improved bounds and new techniques for Davenport--Schinzel sequences and their generalizations
