Proceedings of the 15th annual ACM-SIAM symposium on discrete algorithms

PROCEEDINGS OF THE FIFTEENTH ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS......Page 1
CONTENTS......Page 4
PREFACE......Page 14
ACKNOWLEDGMENTS......Page 15
Session 1A Succinct ordinal trees with level-ancestor queries*......Page 18
Session 1B Finding a Long Directed Cycle......Page 66
Session 1C Variable Length Path Coupling......Page 113
Session 2 INVITED PLENARY ABSTRACT......Page 151
Session 3A Complexity Classification of Network Information Flow Problems......Page 152
Session 3B Approximation Schemes for Multidimensional Packing......Page 196
Session 3C Special Edges, and Approximating the Smallest Directed fc-Edge Connected Spanning Subgraph......Page 244
Session 4A Retroactive Data Structures(extended abstract)......Page 291
Session 4B Improved Upper Bounds for 3-SAT......Page 338
Session 4C A Faster Distributed Protocol for Constructing a Minimum Spanning Tree......Page 369
Session 5A Time Efficient Delaunay Refinement Algorithm......Page 410
Session 5B Adaptive Sampling for Quickselect*......Page 457
Session 5C Minimum Moment Steiner Trees\"......Page 498
Session 6 INVITED PLENARY ABSTRACT......Page 538
Session 7A Interpolation Search for Non-independent Data......Page 539
Session 7B Buffer Minimization using Max-Coloring51......Page 572
Session 7C Trade-offs on the Location of the Core Node in a Network......Page 607
Session 8A When Indexing Equals Compression:Experiments with Compressing Suffix Arrays and Applications......Page 646
Session 8B Dimension Reduction for Ultrametrics......Page 674
Session 8C Frugality in Path Auctions......Page 711
Session 9A Computing Equilibria for Congestion Games with (Im)perfect Information......Page 756
Session 9B Quasiconvex Analysis of Backtracking Algorithms......Page 798
Session 9C Subexponential parameterized algorithms on graphs of bounded-genus and H -minor-free graphs......Page 840
Session 10 INVITED PLENARY ABSTRACT......Page 889
Session 11A Complexities for Generalized Models of Self-Assembly......Page 890
Session 11B Point Containment in the Integer Hull of a Polyhedron1......Page 939
Session 11C Non-migratory Online Deadline Scheduling on Multiprocessors......Page 980
Session 12A On Broadcasting in Heterogenous Networks......Page 1021
Session 12B Randomized Pursuit-Evasion with Limited Visibility......Page 1070
Session 12C On the diameter of the symmetric group:polynomial bounds......Page 1118
AUTHOR INDEX......Page 1148