Algorithmica, Volume 15, 1996

Volume 15, Number 1, January 1996

F. Miller Maley: Testing Homotopic Routability Under Polygonal Wiring Rules. 1-16
G. N. Srinivasa Prasanna, Bruce R. Musicus: The Optimal Control Approach to Generalized Multiprocessor Scheduling. 17-49
Sun Wu, Udi Manber, Eugene W. Myers: A Subquadratic Algorithm for Approximate Limited Expression Matching. 50-67
Shouwen Tang, Kaizhong Zhang, Xiaolin Wu: Fast Algorithms for Minimum Matrix Norm with Application in Computer Graphics. 68-81
Michael B. Dillencourt, Hanan Samet: Using Topological Sweep to Extract the Boundaries of Regions in Maps Represented by Region Quadtrees. 82-102

Special Issue on Parallel Computing

Richard J. Anderson, Paul Beame, Erik Brisson: Parallel Algorithms for Arrangements. 104-125
Michael T. Goodrich, Mujtaba R. Ghouse, J. Bright: Sweep Methods for Parallel Computational Geometry. 126-153
Roberto Tamassia, Jeffrey Scott Vitter: Optimal Cooperative Search in Fractional Cascaded Data Structures. 154-171
David G. Kirkpatrick, Teresa M. Przytycka: Parallel Construction of Binary Trees with Near Optimal Weighted Path Lengt. 172-192
Björn Lisper: Preconditioning Index Set Transformations for Time-Optimal Affine Scheduling. 193-203

Kaizhong Zhang: A Constrained Edit Distance Between Unordered Labeled Trees. 205-222
Herbert Edelsbrunner, Nimish R. Shah: Incremental Topological Flipping Works for Regular Triangulations. 223-241
K. S. Easwarakumar, S. V. Krishnan, C. Pandu Rangan, S. Seshadri: Optimal Parallel Algorithm for Finding st-Ambitus of a Planar Biconnected Graph. 242-255
Bhubaneswar Mishra: Bidirectional Edges Problem: Part I-A Simple Algorithm. 256-286

Ronitt Rubinfeld: Designing Checkers for Programs that Run in Parallel. 287-301
Giuseppe Di Battista, Roberto Tamassia: On-Line Maintenance of Triconnected Components with SPQR-Trees. 302-318
Danny Krizanc, Lata Narayanan, Rajeev Raman: Fast Deterministic Selection on Mesh-Connected Processor Arrays. 319-331
J. L. Nazareth: The Implementation of Linear Programming Algorithms Bases on Homotopies. 332-350
J. Scott Provan, Douglas R. Shier: A Paradigm for Listing (s, t)-Cuts in Graphs. 351-372
Konstantinos Kalpakis, Yelena Yesha: Scheduling Tree DAGs on Parallel Architectures. 373-396

Egon Balas, Jue Xue: Weighted and Unweighted Maximum Clique Algorithms with Upper Bounds from Fractional Coloring. 397-412
Friedhelm Meyer auf der Heide, Brigitte Oesterdiekhoff, Rolf Wanka: Strongly Adaptive Token Distribution. 413-427
Bernard Chazelle, Herbert Edelsbrunner, Leonidas J. Guibas, Micha Sharir, Jorge Stolfi: Lines in Space: Combinatorics and Algorithms. 428-447
Greg N. Frederickson: Searching Among Intervals and Compact Routing Tables. 448-466
Renzo Sprugnoli: Recurrence Relations on Heaps. 467-480
Alberto Apostolico, Franco P. Preparata: Data Structures and Algorithms for the String Statistics Problem. 481-494
Ruth Kuchem, Dorothea Wagner, Frank Wagner: Optimizing Area for Three-Layer Knock-Knee Channel Routing. 495-519

Joseph Cheriyan, Kurt Mehlhorn: Algorithms for Dense Graphs and Networks on the Random Access Computer. 521-549
Peichen Pan, Weiping Shi, C. L. Liu: Area Minimization for Hierarchical Floorplans. 550-571
Yang Cai, M. C. Kong: Nonpreemptive Scheduling of Periodic Tasks in Uni- and Multiprocessor Systems. 572-599
Sanjoy K. Baruah, N. K. Cohen, C. Greg Plaxton, Donald A. Varvel: Proportionate Progress: A Notion of Fairness in Resource Allocation. 600-625
Pankaj K. Agarwal, Marc J. van Kreveld: Connected Component and Simple Polygon Intersection Searching. 626-660