Lecture Notes in Computer Science

Structural complexity theory: Recent surprises.- Approximating maximum independent sets by excluding subgraphs.- Generating sparse spanners for weighted graphs.- Finding the k smallest spanning trees.- The file distribution problem for processor networks.- Translating polygons with applications to hidden surface removal.- Output-sensitive generation of the perspective view of isothetic parallelepipeds.- Graphics in flatland revisited.- The visibility diagram: A data structure for visibility problems and motion planning.- Fast updating of well-balanced trees.- How to update a balanced binary tree with a constant number of rotations.- Ranking trees generated by rotations.- Expected behaviour analysis of AVL trees.- Analysis of the expected search cost in skip lists.- Lower bounds for monotonic list labeling.- Sorting shuffled monotone sequences.- A faster parallel algorithm for a matrix searching problem.- A rectilinear steiner minimal tree algorithm for convex point sets.- Finding shortest paths in the presence of orthogonal obstacles using a combined L 1 and link metric.- Input-sensitive compliant motion in the plane.- Fast algorithms for greedy triangulation.- Star unfolding of a polytope with applications.- Space-sweep algorithms for parametric optimization.- Approximating finite weighted point sets by hyperplanes.- Data structures for Traveling Salesmen.- Efficient parallel algorithms for shortest paths in planar graphs.- The pathwidth and treewidth of cographs.- Canonical representations of partial 2-and 3-trees.- On matroids and hierarchical graphs.- Fast algorithms for two dimensional and multiple pattern matching.- Boyer-Moore approach to approximate string matching.- Complete problems with L-samplable distributions.- Upper envelope onion peeling.- Applications of a semi-dynamic convex hull algorithm.- Intersection queries in sets of disks.- Dynamic partition trees.