Algorithm Engineering and Experimentation

by Goodrich, Michael T.; McGeoch, Catherine C.

• ISBN13: 9783540662273
• ISBN10: 3540662278
• Format: Paperback
• Copyright: 1999-07-01
• Publisher: Springer Verlag

Summary

This book constitutes the thoroughly refereed post-workshop proceedings of the International Workshop on Algorithmic Engineering and Experimentation, ALENEX'99, held in Baltimore, Maryland, USA, in January 1999.The 20 revised full papers presented were carefully selected from a total of 42 submissions during two rounds of reviewing and improvement. The papers are organized in sections on combinatorial algorithms, computational geometry, software and applications, algorithms for NP-hard problems, and data structures.

Table of Contents

Combinatorial Algorithms
Efficient implementation of the WARM-UP algorithm for the construction of length-restricted prefix codes	1	(17)
Ruy Luiz Milidiu
Artur Alves Pessoa
Eduardo Sany Laber
Implementing weighted b-matching algorithms: Insights from a computational study	18	(19)
Matthias Muller-Hannemann
Alexander Schwartz
Designing practical efficient algorithms for symmetric multiprocessors	37	(20)
David R. Helman
Joseph JaJa
Computational Geometry
Circular drawings of biconnected graphs	57	(17)
Janet M. Six
Ioannis G. Tollis
Heuristics and experimental design for bigraph crossing number minimization	74	(20)
Matthias Stallmann
Franc Brglez
Debabrata Gosh
Binary space partitions in Plucker space	94	(20)
David M. Mount
Fan-Tao Pu
Practical point-in-polygon tests using CSG representations of polygons	114	(10)
Robert J. Walker
Jack Snoeyink
Software and Applications
Accessing the internal organization of data structures in the JDSL library	124	(16)
Michael T. Goodrich
Mark Handy
Benoit Hudson
Roberto Tamassia
Object-oriented design of graph oriented data structures	140	(16)
Maurizio Pizzonia
Guiseppe Di Battista
A case study on the cost of geometric computing	156	(21)
Stefan Schirra
Design and implementation of the Fiduccia-Mattheyses heuristic for VLSI netlist partitioning	177	(17)
Andrew E. Caldwell
Andrew B. Kahng
Igor L. Markov
Algorithms for restoration planning in a telecommunications network	194	(16)
S. Cwilich
M. Deng
D. F. Lynch
S. J. Phillips
J. R. Westbrook
Computing the nxm shortest paths efficiently	210	(16)
Tetsuo Shibuya
Image watermarking for copyright protections	226	(20)
Gregory L. Heileman
Carlos E. Pizano
Chaouki T. Abdallah
Algorithms for NP-Hard Problems
A self organizing bin packing heuristic	246	(20)
Janos Csirik
David S. Johnson
Claire Kenyon
Peter W. Shor
Richard R. Weber
Finding the right cutting planes for the TSP	266	(16)
Matthew S. Levine
Obstacle-avoiding Euclidean Steiner Trees in the plane: An exact algorithm	282	(14)
Martin Zachariasen
Pawel Winter
Data Structures
Adaptive algorithms for cache-efficient trie search	296	(16)
Anurag Acharya
Huican Zhu
Kai Shen
Fast priority queues for cached memory	312	(16)
Peter Sanders
Efficient bulk operations on dynamic R-trees	328	(21)
Lars Arge
Klaus H. Hinrichs
Jan Vahrenhold
Jeffrey S. Vitter
Author Index	349