Algorithms and Computation Book

	The Discrepancy Method	1
	Implementing Algorithms and Data Structures: An Educational and Research Perspective	4
	L[subscript [infinity]] Voronoi Diagrams and Applications to VLSI Layout and Manufacturing	9
	Facility Location on Terrains	19
	Computing Weighted Rectilinear Median and Center Set in the Presence of Obstacles	29
	Maximizing Agreement with a Classification by Bounded or Unbounded Number of Associated Words	39
	Disjunctions of Horn Theories and Their Cores	49
	Checking Programs Discreetly: Demonstrating Result-Correctness Efficiently While Concealing It	59
	Two-Layer Planarization in Graph Drawing	69
	Computing Orthogonal Drawings in a Variable Embedding Setting	79
	Dynamic Grid Embedding with Few Bends and Changes	89
	Two New Families of List Update Algorithms	99
	An Optimal Algorithm for On-Line Palletizing at Delivery Industry	109
	On-Line Scheduling of Parallel Jobs with Runtime Restrictions	119
	Testing the Quality of Manufactured Disks and Cylinders	129
	Casting with Skewed Ejection Direction	139
	Repairing Flaws in a Picture Based on a Geometric Representation of a Digital Image	149
	[kappa]-Edge and 3-Vertex Connectivity Augmentation in an Arbitrary Multigraph	159
	Polyhedral Structure of Submodular and Posi-modular Systems	169
	Maximizing the Number of Connections in Optical Tree Networks	179
	Selecting the [kappa] Largest Elements with Parity Tests	189
	Randomized K-Dimensional Binary Search Trees	199
	Randomized O(log log n)-Round Leader Election Protocols in Packet Radio Networks	209
	Random Regular Graphs with Edge Faults: Expansion through Cores	219
	A Quantum Polynomial Time Algorithm in Worst Case for Simon's Problem	229
	Generalized Graph Colorability and Compressibility of Boolean Formulae	237
	On the Complexity of Free Monoid Morphisms	247
	Characterization of Efficiently Solvable Problems on Distance-Hereditary Graphs	257
	Fast Algorithms for Independent Domination and Efficient Domination in Trapezoid Graphs	267
	Finding Planar Geometric Automorphisms in Planar Graphs	277
	A New Approach for Speeding Up Enumeration Algorithms	287
	Hamiltonian Decomposition of Recursive Circulants	297
	Convertibility among Grid Filling Curves	307
	Generalized Self-Approaching Curves	317
	The Steiner Tree Problem in [lambda][subscript 4]-geometry Plane	327
	Approximation and Exact Algorithms for RNA Secondary Structure Prediction and Recognition of Stochastic Context-Free Languages	337
	On the Multiple Gene Duplication Problem	347
	Visibility Queries in Simple Polygons and Applications	357
	Quadtree Decomposition, Steiner Triangulation, and Ray Shooting	367
	Optimality and Integer Programming Formulations of Triangulations in General Dimension	377
	Space-Efficient Approximation Algorithms for MAXCUT and COLORING Semidefinite Programs	387
	A Capacitated Vehicle Routing Problem on a Tree	397
	Approximation Algorithms for Some Optimum Communication Spanning Tree Problems	407
	The Edge-Disjoint Paths Problem is NP-Complete for Partial [kappa]-Trees	417
	Inapproximability Results for Guarding Polygons without Holes	427
	The Inapproximability of Non NP-hard Optimization Problems	437
	An Efficient NC Algorithm for a Sparse [kappa]-Edge-Connectivity Certificate	447
	A Parallel Algorithm for Sampling Matchings from an Almost Uniform Distribution	457
	Optimal Approximate Agreement with Omission Faults	467
	Author Index	477