Proceedings of the Second Symposium on Discrete Algorithms

Finding stabbing lines in 3-dimensional space, M.Pellegrini and P.Shor; space-efficient ray-shooting and intersection searching - algorithms, dynamization and applications, Siu Wing Cheng and Ravi Janardan; edge coloring planar graphs with two outerplanar subgraphs, Lenwood S.Heath; efficient sequential and parallel algorithms for computing recovery points in trees and paths (extended abstract), Marek Chrobak, et al; on-line caching as cache size varies (extended abstract), Neal Young; time-work tradeoffs for parallel graph algorithms, Thomas H.Spencer; offline maintence of planar configurations, John Hershberger and Subhash Suri; circular hulls and obiforms of simple polygons, V.Chandru and R. Venkataraman; dynamic expression trees and their applications (extended abstract), Robert F.Cohen and Roberto Tamassia; a sublinear-time randomized parallel algorithm for the maximum clique problem in perfect graphs, Farod Alizadeh; improved approximation algorithms for shop scheduling problems, David B.Shmoys, et al; the analysis of multidimensional searching in quad-trees, Philippe Flajolet, et al; matching points into noise regions - combinatorial bounds and algorithms, Ester M.Arkin, et al; triangulating three-colored graphs, Sampath K. Kannan and Tandy J.Warnow; recognizing strong connectivity in (dynamic) periodic graphs and its relation in integer programmin g (extended abstract), Muralidharan Kodialam and James B.Orlin; tight bounds on the number of minimum-mean cycle cancellations and related results, Tomasz Radzik and Andrew V.Goldberg; tight bounds on the complexity of the Boyer-Moore string matching algorithm (extended abstract), Richard Cole; computing a face in an arrangement of line segments, Bernard Chazelle, et al; approximation algorithms for planar travelling salesman tours and minimum-length triangulations, Kenneth L.Clarkson; on 0-2 time algorithms for the 2-chain cover problem and related problems, Tze-heng Ma and Jeremy Spinrad; denisty graphs and separators, Gary L.Miller and Stephen A. Vavasis; optimal algorithms for tree partitioning (detailed abstract), Greg N.Frederickson; adaptive heuristics for binary search trees and constant linkage cost, Tony W.Lai and Derick Wood; algorithms and complexity analysis for some flow problems, Edith Cohen and Nimrod Megiddo; a new lower bound techniques and its application - tight lower bound for a polygon triangulation problem, Prakash Ramanan; maintaining the minimal distance of a point set in polylogarithmic time, Michiel Smid; planar geometric location problems and maintaining the width of a planar set, Pankaj K.Agarwal and Micha sharir, Efficient 2 -dimensional approximate matching of non-rectangular figures, Amihood Amir and Martin Farach.