Proceedings of the Fifth Annual ACM-SIAM Symposium on Discrete AlgorithmsSIAM, 01.01.1994 - 735 Seiten The January 1994 Symposium was jointly sponsored by the ACM Special Interest Group for Automata and Computability Theory and the SIAM Activity Group on Discrete Mathematics. Among the topics in 79 (unrefereed) papers: comparing point sets under projection; on-line search in a simple polygon; low- degree tests; maximal empty ellipsoids; roots of a polynomial and its derivatives; dynamic algebraic algorithms; fast comparison of evolutionary trees; an efficient algorithm for dynamic text editing; and tight bounds for dynamic storage allocation. No index. Annotation copyright by Book News, Inc., Portland, OR |
Inhalt
Comparing Point Sets Under Projection | 1 |
OnLine Search in a Simple Polygon | 8 |
On Degeneracy in Geometric Computations | 16 |
Surface Approximation and Geometric Partitions | 24 |
Reliable Benchmarks Using Numerical Instability | 34 |
An Effective Additive Basis for the Integers | 44 |
Lowdegree Tests | 57 |
Linear and Onlogn Time MinimumCost Matching | 65 |
Optimal Constructions of Hybrid Algorithms | 372 |
Linear Programs for Randomized OnLine Algorithms | 382 |
Optimal Prediction for Prefecting in the Worst Case | 392 |
Design of Online Algorithms Using Hitting Times | 402 |
Efficient Routing and Scheduling Algorithms for Optical | 412 |
Using Randomized Sparsification to Approximate Minimum | 424 |
Polynomial Time Algorithms for Some Evacuation Problems | 433 |
A Las Vegas On2 38 Algorithm for the Cardinality of | 442 |
Average Case Analysis of Dynamic Geometric Optimization | 77 |
A NearLinear Algorithm for the Planar Segment Center | 87 |
Maximal Empty Ellipsoids | 98 |
Scheduling Parallel Tasks to Minimize Average Response Time | 112 |
Minimizing Channel Density by Lateral Shifting | 122 |
A Better Algorithm for an Ancient Scheduling Problem | 132 |
On the Greedy Heuristic for Matchings | 141 |
New Results on the Old kOpt Algorithm for the | 150 |
Clustering for Faster Network Simplex Pivots | 160 |
Scheduling Malleable and Nonmalleable Parallel Tasks | 167 |
Approximating the Minimum Equivalent Diagraph | 177 |
Approximate Data Structures with Applications | 187 |
An Optimal RAM Implementation of Catenable | 195 |
Dynamic TwoConnectivity with Backtracking | 204 |
Maintaining Dynamic Sequences Under EqualityTests | 213 |
Improved Approximation Algorithms for Network | 223 |
A Scaling Technique for Better Network Design | 233 |
Optimal Parallel Approximation Algorithms for Prefix Sums | 241 |
Neighborhood Preserving Hashing and Approximate Queries | 251 |
New Techniques for Approximating Complex Polynomial Zeros | 260 |
Roots of a Polynomial and its Derivatives | 271 |
The Complexity of Resolvent Resolved | 280 |
Dynamic Algebraic Algorithms | 290 |
Online Interval Scheduling | 302 |
Competitive NonPreemptive Call Control | 312 |
Competitive Routing of Virtual Circuits with Unknown | 321 |
Learning Binary Matroid Ports | 328 |
Approximately Counting Hamilton Cycles in Dense Graphs | 336 |
Approximation Algorithms for the Vertex Feedback Set Problem | 344 |
Computational Experience with an Approximation Algorithm | 355 |
Approximating Maximum Independent Set in Bounded Degree | 365 |
Moments of Inertia and Graph Separators | 452 |
Shallow Excluded Minors and Improved Graph Decompositions | 462 |
Reconstructing a History of Recombinations from a Set | 471 |
Fast Comparison of Evolutionary Trees | 481 |
Physical Mapping of Chromosomes Using Unique Probes | 489 |
The Subtree Max Gap Problem with Application to Parallel | 501 |
Computing the Covers of a String in Linear Time | 511 |
Path Problems in SkewSymmetric Graphs | 526 |
LinearTime Modular Decomposition and Efficient Transitive | 536 |
Spanning Trees Short or Small | 546 |
Generating LowDegree 2Spanners | 556 |
The Design of Playoff | 564 |
An Optimal Algorithm for Approximate Nearest Neighbor | 573 |
Queueing Analysis of Oblivious PacketRouting Networks | 583 |
Testable Algorithms for SelfAvoiding Walks | 593 |
Optimal Construction of EdgeDisjoint Paths in Random | 603 |
Optimal Randomized Parallel Algorithms for Computing | 613 |
An Efficient Parallel Algorithm for the General Planar | 622 |
A Sublinear Parallel Algorithm for Stable Matching | 632 |
Accounting for Contention in Parallel | 638 |
Optimum Parallel Computations with Banded Matrices | 649 |
Optimal Parallel Sorting in MultiLevel Storage | 659 |
Derandomizing Algorithms for Routing and Sorting on Meshes | 669 |
On Optimal Strategies for Searching in Presence of Errors | 680 |
Matching Nuts and Bolts | 690 |
An Efficient Algorithm for Dynamic Text Indexing | 697 |
Pattern Matching in Zcompressed Files | 705 |
Two and Higher Dimensional Pattern Matching in Optimal | 715 |
Tight Bounds for Dynamic Storage Allocation | 724 |
| 733 | |
Andere Ausgaben - Alle anzeigen
Häufige Begriffe und Wortgruppen
apply approximation algorithm assigned assume bipartite graph circuit color competitive ratio component Computer Science connected consider constant construction contains convex hull corresponding cost cycle data structure decomposition defined deleted denote distance dynamic edges element endpoints flow function given graph G implementation input integer interval iteration least Lemma length linear linear program lower bound Markov chain matching matrix matroid maximum minimum cut minimum spanning tree neighbor nodes O(log O(n² on-line operations optimal output P₁ pair parallel partition path performance phase planar player points polynomial PRAM prefetcher prefix sums probability problem Proc processors Proof prove query queue random randomized algorithm recursively rithm running satisfies schedule segment sequence shortest solution solve spanning tree step subgraph subset Symposium task technique Theorem tion triangle undirected graph update upper bound vertices wavelengths weight zero