Improved lower bounds on the length of Davenport-Schinzel sequences
From MaRDI portal
Publication:1119587
DOI10.1007/BF02122559zbMath0672.05015OpenAlexW2093966347MaRDI QIDQ1119587
Publication date: 1988
Published in: Combinatorica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/bf02122559
Analysis of algorithms and problem complexity (68Q25) Extremal problems in graph theory (05C35) Enumerative combinatorics (05A99)
Related Items
Planar realizations of nonlinear Davenport-Schinzel sequences by segments, On the two-dimensional Davenport-Schinzel problem, A survey of motion planning and related geometric algorithms, Sharp upper and lower bounds on the length of general Davenport-Schinzel sequences, Arrangements of curves in the plane --- topology, combinatorics, and algorithms, Generalized Davenport-Schinzel sequences and their 0-1 matrix counterparts, An efficient motion-planning algorithm for a convex polygonal object in two-dimensional polygonal space, On the number of critical free contacts of a convex polygonal object moving in two-dimensional polygonal space, The upper envelope of piecewise linear functions and the boundary of a region enclosed by convex plates: Combinatorial analysis, An Output-Sensitive Convex Hull Algorithm for Planar Objects
Cites Work
- Generalized Voronoi diagrams for a ladder. II: Efficient construction of the diagram
- Nonlinearity of Davenport-Schinzel sequences and of generalized path compression schemes
- Almost linear upper bounds on the length of general Davenport-Schinzel sequences
- On the number of critical free contacts of a convex polygonal object moving in two-dimensional polygonal space
- On the shortest paths between two convex polyhedra
- A Combinatorial Problem Connected with Differential Equations
- A combinatorial problem connected with differential equations II
