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