%{search_type} search results

This book constitutes the refereed proceedings of the 7th Annual European Symposium on Algorithms, ESA '99, held in Prague, Czech Republic, in July 1999. The 44 revised papers presented were carefully reviewed and selected from a total of 122 submissions. All areas of algorithmic research are covered, in particular approximation algorithms, combinatorial optimization, computational mathematics, computational science, databases and information retrieval, graph computations, network algorithms, online algorithms, pattern matching, data compression, parallel algorithms, distributed algorithms, and sequential algorithms.

This book constitutes the refereed proceedings of the 5th Annual International European Symposium on Algorithms, ESA'97, held in Graz, Austria, September 1997. The 38 revised full papers presented were selected from 112 submitted papers. The papers address a broad spectrum of theoretical and applicational aspects in algorithms theory and design. Among the topics covered are approximation algorithms, graph and network algorithms, combinatorial optimization, computational biology, computational mathematics, data compression, distributed computing, evolutionary algorithms, neural computing, online algorithms, parallel computing, pattern matching, and others.

• Part I. Introducing Macaulay
• 2:
• 1. Ideals, Varieties and Macaulay 2 by Bernd Sturmfels.-
• 2. Projective Geometry and Homological Algebra by David Eisenbud.-
• 3. Data Types, Functions, and Programming by Daniel R. Grayson and Michael E. Stillman.-
• 4. Teaching the Geometry of Schemes by Gregory G. Smith and Bernd Sturmfels.- Part II. Mathematical Computations:
• 5. Monomial Ideals by Serkan Hosten and Gregory G. Smith.-
• 6. From Enumerative Geometry to Solving Systems of Polynomial Equations by Frank Sottile.-
• 7. Resolutions and Cohomology over Complete Intersections by Luchezar L. Avramov and Daniel R. Grayson.-
• 8. Algorithms for the Toric Hilbert Scheme by Stillman, Bernd Sturmfels, and Rekha Thomas.-
• 9. Sheaf Algorithms Using the Exterior Algebra by Wolfram Decker and David Eisenbud.-
• 10. Needles in a Haystack: Special Varieties via Small Fields by Frank-Olaf Schreyer and Fabio Tonoli.- 11.D-modules and Cohomology of Varieties by Uli Walther.
• (source: Nielsen Book Data)

This book presents algorithmic tools for algebraic geometry and experimental applications of them. It also introduces a software system in which the tools have been implemented and with which the experiments can be carried out. Macaulay 2 is a computer algebra system devoted to supporting research in algebraic geometry, commutative algebra, and their applications. The reader of this book will encounter Macaulay 2 in the context of concrete applications and practical computations in algebraic geometry. The expositions of the algorithmic tools presented here are designed to serve as a useful guide for those wishing to bring such tools to bear on their own problems. These expositions will be valuable to both the users of other programs similar to Macaulay 2 (for example, Singular and CoCoA) and those who are not interested in explicit machine computations at all. The first part of the book is primarily concerned with introducing Macaulay2, whereas the second part emphasizes the mathematics.
(source: Nielsen Book Data)

• Optimum Tracking in Dynamic Environments.- Explicit Memory Schemes for Evolutionary Algorithms in Dynamic Environments.- Particle Swarm Optimization in Dynamic Environments.- Evolution Strategies in Dynamic Environments.- Orthogonal Dynamic Hill Climbing Algorithm: ODHC.- Genetic Algorithms with Self-Organizing Behaviour in Dynamic Environments.- Learning and Anticipation in Online Dynamic Optimization.- Evolutionary Online Data Mining: An Investigation in a Dynamic Environment.- Adaptive Business Intelligence: Three Case Studies.- Evolutionary Algorithms for Combinatorial Problems in the Uncertain Environment of the Wireless Sensor Networks.- Approximation of Fitness Functions.- Individual-based Management of Meta-models for Evolutionary Optimization with Application to Three-Dimensional Blade Optimization.- Evolutionary Shape Optimization Using Gaussian Processes.- A Study of Techniques to Improve the Efficiency of a Multi-Objective Particle Swarm Optimizer.- An Evolutionary Multi-objective Adaptive Meta-modeling Procedure Using Artificial Neural Networks.- Surrogate Model-Based Optimization Framework: A Case Study in Aerospace Design.- Handling Noisy Fitness Functions.- Hierarchical Evolutionary Algorithms and Noise Compensation via Adaptation.- Evolving Multi Rover Systems in Dynamic and Noisy Environments.- A Memetic Algorithm Using a Trust-Region Derivative-Free Optimization with Quadratic Modelling for Optimization of Expensive and Noisy Black-box Functions.- Genetic Algorithm to Optimize Fitness Function with Sampling Error and its Application to Financial Optimization Problem.- Search for Robust Solutions.- Single/Multi-objective Inverse Robust Evolutionary Design Methodology in the Presence of Uncertainty.- Evolving the Tradeoffs between Pareto-Optimality and Robustness in Multi-Objective Evolutionary Algorithms.- Evolutionary Robust Design of Analog Filters Using Genetic Programming.- Robust Salting Route Optimization Using Evolutionary Algorithms.- An Evolutionary Approach For Robust Layout Synthesis of MEMS.- A Hybrid Approach Based on Evolutionary Strategies and Interval Arithmetic to Perform Robust Designs.- An Evolutionary Approach for Assessing the Degree of Robustness of Solutions to Multi-Objective Models.- Deterministic Robust Optimal Design Based on Standard Crowding Genetic Algorithm.
• (source: Nielsen Book Data)

This book compiles recent advances of evolutionary algorithms in dynamic and uncertain environments within a unified framework. The book is motivated by the fact that some degree of uncertainty is inevitable in characterizing any realistic engineering systems. Discussion includes representative methods for addressing major sources of uncertainties in evolutionary computation, including handle of noisy fitness functions, use of approximate fitness functions, search for robust solutions, and tracking moving optimums.
(source: Nielsen Book Data)

• Analysis of Shellsort and related algorithms
• Drawing with colors
• Approximating the unsatisfiability threshold of random formulas (Extended Abstract)
• Preemptive weighted completion time scheduling of parallel jobs
• Approximation algorithms for dynamic storage allocation
• Positive linear programming, parallel approximation and PCP's
• Scheduling jobs with communication delays: Using infeasible solutions for approximation
• Randomization of search trees by subtree size
• Efficient dynamic method-lookup for object oriented languages
• Priority queues: Small, monotone and trans-dichotomous
• Simulated Annealing and its problems to color graphs
• The capacitated K-center problem
• A unified local ratio approximation of node-deletion problems
• Approximation algorithms for connected dominating sets
• Greedy algorithms for the shortest common superstring that are asymtotically optimal
• On the depth of randomly generated circuits
• The analysis of linear probing hashing with buckets
• Parallel algorithms for partitioning sorted sets and related problems
• Fast generation of random permutations via networks simulation
• On the Parallel Dynamic Dictionary Matching problem: New results with applications
• Parallel algorithms for series parallel graphs
• Parallel complexity of householder QR factorization
• Reporting red-blue intersections between two sets of connected line segments
• Matching convex shapes with respect to the symmetric difference
• On minimum-area hulls
• Negative-cycle detection algorithms
• A new regular grammar pattern matching algorithm
• Lempel-Ziv index for q-grams
• Computing upper and lower bounds on textile nesting problems
• On-line and off-line approximation algorithms for vector covering problems
• Competitive analysis of randomized paging algorithms
• On-line competitive algorithms for call admission in optical networks
• Race-condition detection in parallel computation with semaphores (extended abstract)
• Efficient wavelength routing on directed fiber trees
• A lower bound for nearly minimal adaptive and hot potato algorithms
• The structure of circular decomposable metrics
• Faster algorithms for subgraph isomorphism of?-connected partial?-trees
• Planar spanners and approximate shortest path queries among obstacles in the plane
• A new approach to optimal planning of robot motion on a tree with obstacles
• Generalized streets revisited
• Computational aspects of organization theory.

"This book constitutes the refereed proceedings of the 4th European Symposium on Algorithms, ESA '96, held in Barcelona, Spain, in September 1996. The book presents 40 revised full papers selected from 124 submissions; also are included extended abstracts of two invited presentations. The papers included cover all research areas on algorithms and their analysis as it is carried out in the fields of computer science, discrete applied and algorithmic mathematics, operations research, and all other areas of algorithms-oriented research, design and analysis."--PUBLISHER'S WEBSITE

• On mixed connectivity certificates.- Truly efficient parallel algorithms: c-optimal multisearch for an extension of the BSP model.- Optimal parallel shortest paths in small treewidth digraphs.- Shared memory simulations with triple-logarithmic delay.- Implementing shared memory on multi-dimensional meshes and on the fat-tree.- Beyond the worst-case bisection bound: Fast sorting and ranking on meshes.- Fast deterministic simulation of computations on faulty parallel machines.- Average circuit depth and average communication complexity.- Packing trees.- Sometimes travelling is easy: The master tour problem.- Interval graphs with side (and size) constraints.- Maximum skew-symmetric flows.- Certificates and fast algorithms for biconnectivity in fully-dynamic graphs.- On the all-pairs shortest path algorithm of Moffat and Takaoka.- Fully Dynamic Transitive Closure in plane dags with one source and one sink.- Planarity for clustered graphs.- A geometric approach to betweenness.- Efficient computation of the geodesic Voronoi diagram of points in a simple polygon.- Linear size binary space partitions for fat objects.- Geometric pattern matching in d-dimensional space.- Finding the constrained Delaunay triangulation and constrained Voronoi diagram of a simple polygon in linear-time.- External-memory algorithms for processing line segments in geographic information systems.- Optimized binary search and text retrieval.- On using q-gram locations in approximate string matching.- Routing with bounded buffers and hot-potato routing in vertex-symmetric networks.- Load balancing for response time.- Self-simulation for the Passive Optical Star model.- Computing the agreement of trees with bounded degrees.- Approximation algorithms for feasible cut and multicut problems.- On parallel versus sequential approximation.- An efficient and effective approximation algorithm for the Map Labeling Problem.- Approximating the bandwidth for asteroidal triple-free graphs.- Near-optimal distributed edge coloring.- The centroid of points with approximate weights.- 0/1-Integer programming: Optimization and Augmentation are equivalent.- The online transportation problem.- A polyhedral approach to planar augmentation and related problems.- Optimal layouts on a chain ATM network.- Efficient Dynamic-Resharing "Verifiable Secret Sharing" against mobile adversary.- Adaptive Video on Demand.- The binomial transform and its application to the analysis of skip lists.- An optimal parallel algorithm for digital curve segmentation using hough polygons and monotone function search.- Fast skeleton construction.
• (source: Nielsen Book Data)

This book consitutes the proceedings of the Third Annual European Symposium on Algorithms, ESA '95, held in Corfu, Greece in September 1995. The volume presents 42 full revised papers selected during a careful refereeing process from a total of 119 submissions; in addition, there is a prominent keynote address. This year, the scope has been further expanded to new areas of computational endeavour in science; the book covers many aspects of algorithms research and application ranging from combinatorial mathematics to hardware design.
(source: Nielsen Book Data)

• Differential Evolution.- Neoteric Differential Evolution.- Strategies of Search.- Exploration and Exploitation.- New Performance Measures.- Transversal Differential Evolution.- On Analogy with Some Other Algorithms.- Energetic Selection Principle.- On Hybridization of Differential Evolution.- Applications.- End Notes.
• (source: Nielsen Book Data)

Individuals and enterprises are looking for optimal solutions for the problems they face. Most problems can be expressed in mathematical terms, and so the methods of optimization render a significant aid. This book details the latest achievements in optimization. It offers comprehensive coverage on Differential Evolution, presenting revolutionary ideas in population-based optimization and shows the best known metaheuristics through the prism of Differential Evolution.
(source: Nielsen Book Data)

• Invited Presentation.- The Discrepancy Method.- Implementing Algorithms and Data Structures: An Educational and Research Perspective.- Geometry I.- L? Voronoi Diagrams and Applications to VLSI Layout and Manufacturing.- Facility Location on Terrains.- Computing Weighted Rectilinear Median and Center Set in the Presence of Obstacles.- Complexity I.- Maximizing Agreement with a Classification by Bounded or Unbounded number of Associated Words.- Disjunctions of Horn Theories and Their Cores.- Checking Programs Discreetly: Demonstrating Result-Correctness Efficiently While Concealing It.- Graph Drawing.- Two-Layer Planarization in Graph Drawing.- Computing Orthogonal Drawings in a Variable Embedding Setting.- Dynamic Grid Embedding with Few Bends and Changes.- On-Line Algorithm and Scheduling.- Two New Families of List Update Algorithms.- An Optimal Algorithm for On-Line Palletizing at Delivery Industry.- On-Line Scheduling of Parallel Jobs with Runtime Restrictions.- CAD/CAM and Graphics.- Testing the Quality of Manufactured Disks and Cylinders.- Casting with Skewed Ejection Direction.- Repairing Flaws in a Picture Based on a Geometric Representation of a Digital Image.- Graph Algorithm I.- k-Edge and 3-Vertex Connectivity Augmentation in an Arbitrary Multigraph.- Polyhedral Structure of Submodular and Posi-modular Systems.- Maximizing the number of Connections in Optical Tree Networks.- Best Paper Presentation.- Selecting the k Largest Elements with Parity Tests.- Randomized Algorithm.- Randomized K-Dimensional Binary Search Trees.- Randomized O(log log n)-Round Leader Election Protocols in Packet Radio Networks.- Random Regular Graphs with Edge Faults: Expansion through Cores.- Complexity II.- A Quantum Polynomial Time Algorithm in Worst Case for Simon's Problem.- Generalized Graph Colorability and Compressibility of Boolean Formulae.- On the Complexity of Free Monoid Morphisms.- Graph Algorithm II.- Characterization of Efficiently Solvable Problems on Distance-Hereditary Graphs.- Fast Algorithms for Independent Domination and Efficient Domination in Trapezoid Graphs.- Finding Planar Geometric Automorphisms in Planar Graphs.- Combinatorial Problem.- New Approach for Speeding Up Enumeration Algorithms.- Hamiltonian Decomposition of Recursive Circulants.- Convertibility among Grid Filling Curves.- Geometry II.- Generalized Self-Approaching Curves.- The Steiner Tree Problem in ?4-geometry Plane.- Computational Biology.- Approximation and Exact Algorithms for RNA Secondary Structure Prediction and Recognition of Stochastic Context-Free Languages.- On the Multiple Gene Duplication Problem.- Geometry III.- Visibility Queries in Simple Polygons and Applications.- Quadtree Decomposition, Steiner Triangulation, and Ray Shooting.- Optimality and Integer Programming Formulations of Triangulations in General Dimension.- Approximation Algorithm.- Space-Efficient Approximation Algorithms for MAXCUT and COLORING Semidefinite Programs.- A Capacitated Vehicle Routing Problem on a Tree.- Approximation Algorithms for Some Optimum Communication Spanning Tree Problems.- Complexity III.- The Edge-Disjoint Paths Problem is NP-Complete for Partial k-Trees.- Inapproximability Results for Guarding Polygons without Holes.- The Inapproximability of Non NP-hard Optimization Problems.- Parallel and Distributed Algorithm.- An Efficient NC Algorithm for a Sparse k-Edge-Connectivity Certificate.- A Parallel Algorithm for Sampling Matchings from an Almost Uniform Distribution.- Optimal Approximate Agreement with Omission Faults.
• (source: Nielsen Book Data)

The papers in this volume were selected for presentation at the Ninth Annual International Symposium on Algorithms and Computation (ISAAC'98), heldonDecember14-16,1998inTaejon, Korea.P- viousmeetingswereheldinTokyo(1990), Taipei(1991), Nagoya (1992), HongKong(1993), Beijing(1994), Cairns(1995), Osaka (1996), andSingapore(1997). The symposium was jointly sponsored by Korea Advanced - stitute of Science and Technology (KAIST) and Korea Information Science Society (KISS) to commemorate its 25th anniversary in - operationwithMinistryofInformationandCommunication, Korea InformationSocietyDevelopmentInstitute, andKoreaScienceand Engineering Foundation. Inresponsetothecallforpapers, 102extendedabstractswere submitted from 21 countries. Each submitted paper was reported on byatleastfourprogramcommitteemembers, withtheassistance ofreferees, asindicatedbytherefereelistfoundintheseproce- ings. There were many more acceptable papers than there was space availableinthesymposiumschedule, andtheprogramcommittee's task was extremely di?cult. The 47 papers selected for presentation hadatotalof105authors, residentasfollows:Japan24, Germany 17, UnitedStateofAmerica15, Taiwan10, HongKongandKorea 6each, Spain5, SwitzerlandandAustralia4each, Austria, Canada, andFrance3each, ItalyandNetherlands2each, andGreece1. We thank all program committee members and their referees fortheirexcellentwork, especiallygiventhedemandingtimec- straints; they gave the symposium its distinctive character. We thank all who submitted papers for consideration: they all contributed to the high quality of the symposium. Finally, wethankallthepeoplewhoworkedhardtoputinplace the logistical arrangements of the symposium - our colleagues and our graduate students. It is their hard work that made the sym- sium possible and enjoyable.
(source: Nielsen Book Data)

The goal of machine learning is to program computers to use example data or past experience to solve a given problem. Many successful applications of machine learning exist already, including systems that analyze past sales data to predict customer behavior, optimize robot behavior so that a task can be completed using minimum resources, and extract knowledge from bioinformatics data. The second edition of Introduction to Machine Learning is a comprehensive textbook on the subject, covering a broad array of topics not usually included in introductory machine learning texts. In order to present a unified treatment of machine learning problems and solutions, it discusses many methods from different fields, including statistics, pattern recognition, neural networks, artificial intelligence, signal processing, control, and data mining. All learning algorithms are explained so that the student can easily move from the equations in the book to a computer program. The text covers such topics as supervised learning, Bayesian decision theory, parametric methods, multivariate methods, multilayer perceptrons, local models, hidden Markov models, assessing and comparing classification algorithms, and reinforcement learning. New to the second edition are chapters on kernel machines, graphical models, and Bayesian estimation; expanded coverage of statistical tests in a chapter on design and analysis of machine learning experiments; case studies available on the Web (with downloadable results for instructors); and many additional exercises. All chapters have been revised and updated. Introduction to Machine Learning can be used by advanced undergraduates and graduate students who have completed courses in computer programming, probability, calculus, and linear algebra. It will also be of interest to engineers in the field who are concerned with the application of machine learning methods.
(source: Nielsen Book Data)

The goal of machine learning is to program computers to use example data or past experience to solve a given problem. Many successful applications of machine learning exist already, including systems that analyze past sales data to predict customer behavior, optimize robot behavior so that a task can be completed using minimum resources, and extract knowledge from bioinformatics data. The second edition of Introduction to Machine Learning is a comprehensive textbook on the subject, covering a broad array of topics not usually included in introductory machine learning texts. In order to present a unified treatment of machine learning problems and solutions, it discusses many methods from different fields, including statistics, pattern recognition, neural networks, artificial intelligence, signal processing, control, and data mining. All learning algorithms are explained so that the student can easily move from the equations in the book to a computer program. The text covers such topics as supervised learning, Bayesian decision theory, parametric methods, multivariate methods, multilayer perceptrons, local models, hidden Markov models, assessing and comparing classification algorithms, and reinforcement learning. New to the second edition are chapters on kernel machines, graphical models, and Bayesian estimation; expanded coverage of statistical tests in a chapter on design and analysis of machine learning experiments; case studies available on the Web (with downloadable results for instructors); and many additional exercises. All chapters have been revised and updated. Introduction to Machine Learning can be used by advanced undergraduates and graduate students who have completed courses in computer programming, probability, calculus, and linear algebra. It will also be of interest to engineers in the field who are concerned with the application of machine learning methods.
(source: Nielsen Book Data)

• Preface.- Basic Graph Theory.- Algorithms and Complexity.- Shortest Paths.- Spanning Trees.- The Greedy Algorithm.- Flows.- Combinatorial Applications.- Connectivity and Depth First Search.- Colorings.- Circulations.- The Network Simplex Algorithm.- Matchings.- Weighted Matchings.- A Hard Problem: The TSP.- Appendix A: Solutions.- Appendix B: List of Symbols.- References.- Index.
• (source: Nielsen Book Data)

From the reviews of the first edition:"...The book is a first class textbook and seems to be indispensable for everybody who has to teach combinatorial optimization. It is very helpful for students, teachers, and researchers in this area. The author finds a striking synthesis of nice and interesting mathematical results and practical applications...the author pays much attention to the inclusion of well-chosen exercises. The reader does not remain helpless; solutions or at least hints are given in the appendix. Except for some small basic mathematical and algorithmic knowledge the book is self-contained..." Mathematical Reviews 2002This thoroughly revised new edition offers a new chapter on the network simplex algorithm and a section on the five color theorem. Moreover, numerous smaller changes and corrections have been made and several recent developments have been discussed and referenced.
(source: Nielsen Book Data)

• Foundations and ideas
• Principal model types
• Approaches to model building
• Fundamental concepts of fuzzy logic
• Fundamental concepts of fuzzy systems
• Fuzzy SQL and intelligent queries
• Fuzzy clustering
• Fuzzy rule induction
• Fundamental concepts of genetic algorithms
• Genetic resource scheduling optimization
• Genetic tuning of fuzzy models.

Fuzzy Modeling and Genetic Algorithms for Data Mining and Exploration is a handbook for analysts, engineers, and managers involved in developing data mining models in business and government. As youll discover, fuzzy systems are extraordinarily valuable tools for representing and manipulating all kinds of data, and genetic algorithms and evolutionary programming techniques drawn from biology provide the most effective means for designing and tuning these systems. You dont need a background in fuzzy modeling or genetic algorithms to benefit, for this book provides it, along with detailed instruction in methods that you can immediately put to work in your own projects. The author provides many diverse examples and also an extended example in which evolutionary strategies are used to create a complex scheduling system. * Written to provide analysts, engineers, and managers with the background and specific instruction needed to develop and implement more effective data mining systems. * Helps you to understand the trade-offs implicit in various models and model architectures. * Provides extensive coverage of fuzzy SQL querying, fuzzy clustering, and fuzzy rule induction. * Lays out a roadmap for exploring data, selecting model system measures, organizing adaptive feedback loops, selecting a model configuration, implementing a working model, and validating the final model. * In an extended example, applies evolutionary programming techniques to solve a complicated scheduling problem. * Presents examples in C, C++, Java, and easy-to-understand pseudo-code. * Extensive online component, including sample code and a complete data mining workbench.

• Invited Talk
• The Engineering of Some Bipartite Matching Programs
• Session 1(a)
• Data Structure I
• General Splay: A Basic Theory and Calculus
• Static Dictionaries Supporting Rank
• Session 1(b)
• Parallel & Distributed Computing I
• Multiple Spin-Block Decisions
• Asynchronous Random Polling Dynamic Load Balancing
• Session 2(a)
• Approximate Algorithm I
• Simple Approximation Algorithms for MAXNAESP and Hypergraph 2-colarability
• Hardness of Approximating Independent Domination in Circle Graphs
• Constant-Factor Approximation Algorithms for Domination Problems on Circle Graphs
• Session 2(b)
• Computational Intelligence
• Ordered Binary Decision Diagrams as Knowledge-Bases
• Hard Tasks for Weak Robots: The Role of Common Knowledge in Pattern Formation by Autonomous Mobile Robots
• Session 3(a)
• Online Algorithm
• On-Line Load Balancing of Temporary Tasks Revisited
• Online Routing in Triangulations
• Session 3(b)
• Complexity Theory I
• The Query Complexity of Program Checking by Constant-Depth Circuits
• Tree-Like Resolution Is Superpolynomially Slower Than DAG-Like Resolution for the Pigeonhole Principle
• Session 4(a)
• Approximate Algorithm II
• Efficient Approximation Algorithms for Multi-label Map Labeling
• Approximation Algorithms in Batch Processing
• Session 4(b)
• Graph Algorithm I
• LexBFS-Ordering in Asteroidal Triple-Free Graphs
• Parallel Algorithms for Shortest Paths and Related Problems on Trapezoid Graphs
• Invited Talk
• Approximation Algorithms for Some Clustering and Classification Problems
• Session 5(a)
• Computational Geometry I
• How Many People Can Hide in a Terrain?
• Carrying Umbrellas: An Online Relocation Problem on Graphs
• Session 5(b)
• Parallel & Distributed Computing II
• Survivable Networks with Bounded Delay: The Edge Failure Case
• Energy-Efficient Initialization Protocols for Ad-hoc Radio Networks
• Session 6(a)
• Data Structure II
• Constructing the Suffix Tree of a Tree with a Large Alphabet
• An O(1) Time Algorithm for Generating Multiset Permutations
• Session 6(b)
• Complexity Theory II
• Upper Bounds for MaxSat: Further Improved
• A Linear Time Algorithm for Recognizing Regular Boolean Functions
• Session 7(a)
• Computational Geometry II
• Station Layouts in the Presence of Location Constraints
• Reverse Center Location Problem
• Session 7(b)
• Algorithms in Practice
• Performance Comparison of Linear Sieve and Cubic Sieve Algorithms for Discrete Logarithms over Prime Fields
• External Memory Algorithms for Outerplanar Graphs
• Session 8(a)
• Approximate Algorithm III
• A New Approximation Algorithm for the Capacitated Vehicle Routing Problem on a Tree
• Approximation Algorithms for Channel Assignment with Constraints
• Session 8(b)
• Graph Algorithm II
• Algorithms for Finding Noncrossing Steiner Forests in Plane Graphs
• A Linear Algorithm for Finding Total Colorings of Partial k-Trees
• Invited Talk
• Topology-Oriented Approach to Robust Geometric Computation
• Session 9(a)
• Approximate Algorithm IV
• Approximating Multicast Congestion
• Approximating the Minimum k-way Cut in a Graph via Minimum 3-way Cuts
• Session 9(b)
• Parallel & Distributed Computing III
• Online Scheduling of Parallel Communications with Individual Deadlines
• A Faster Algorithm for Finding Disjoint Paths in Grids
• Session 10(a)
• Computational Geometry III
• Output-Sensitive Algorithms for Uniform Partitions of Points
• Convexifying Monotone Polygons
• Session 10(b)
• Graph Algorithm III
• Bisecting Two Subsets in 3-Connected Graphs
• Generalized Maximum Independent Sets for Trees in Subquadratic Time.

This book constitutes the refereed proceedings of the 10th International Symposium on Algorithms and Computation, ISAAC'99, held in Chennai, India, in December 1999. The 40 revised full papers presented together with four invited contributions were carefully reviewed and selected from 71 submissions. Among the topics covered are data structures, parallel and distributed computing, approximation algorithms, computational intelligence, online algorithms, complexity theory, graph algorithms, computational geometry, and algorithms in practice.

• Solving NP-hard combinatorial problems in the practical sense Invited presentation
• Airline crew-scheduling problem with many irregular flights
• Practical approach to a facility location problem for large-scale logistics
• Hard instance generation for SAT
• Playing tetris on meshes and multi-dimensional Shearsort
• Formulation of the addition-shift-sequence problem and its complexity
• Weighted and unweighted selection algorithms for k sorted sequences
• An adaptive distributed fault-tolerant routing algorithm for the star graph
• Multi-color routing in the undirected hypercube
• Competitive source routing on tori and meshes
• Algorithms for enumerating all perfect, maximum and maximal matchings in bipartite graphs
• Augmenting edge and vertex connectivities simultaneously
• Two-face horn extensions
• Decremental maintenance of reachability in hypergraphs and minimum models of horn formulae
• Algorithmic analysis of multithreaded algorithms
• A characterization of planar graphs by pseudo-line arrangements
• Optimal fault-tolerant broadcasting in trees
• A theoretical framework of hybrid approaches to MAX SAT
• Exponential lower bounds on the size of OBDDs representing integer division
• On-line versus off-line in money-making strategies with brokerage
• Decision-making by hierarchies of discordant agents
• A new efficient off-line anonymous cash scheme
• Approximating unweighted connectivity problems in parallel
• A randomized linear work EREW PRAM algorithm to find a minimum spanning forest
• Efficient parallel algorithms for planar st-graphs
• Peg-solitaire, string rewriting systems and finite automata
• On the size of probabilistic formulae
• Homophonic coding with logarithmic memory size
• Complexity and modeling aspects of mesh refinement into quadrilaterals
• Topology oriented vs. exact arithmetic
• Experience in implementing the three-dimensional convex hull algorithm
• The complexity of learning branches and strategies from queries
• Singularities make spatial join scheduling hard
• A faster one-dimensional topological compaction algorithm
• Algorithms for finding optimal disjoint paths around a rectangle
• An algorithm for finding a region with the minimum total L 1 from prescribed terminals
• On defect sets in bipartite graphs (extended abstract)
• Dynamic programming on distance-hereditary graphs
• On the equivalence in complexity among basic problems on bipartite and parity graphs
• All-cavity maximum matchings
• Fast algorithms for computing ?-Skeletons and their relatives
• A branch-and-cut approach for minimum weight triangulation
• An efficient approximation scheme for the subset-sum problem
• Competitive call control in mobile networks
• Generalized swap-with-parent schemes for self-organizing sequential linear lists.

This book constitutes the refereed proceedings of the 8th International Symposium on Algorithms and Computation, ISAAC'97, held in Singapore in December 1997. The 42 revised full papers presented were selected from a total of 98 submissions. The scope of the volume spans the whole area of algorithms from discrete mathematics and complexity theory to algorithms design and evaluation in a variety of applicational areas. Among the topics addressed are scheduling and logistics, networking and routing, combinatorial optimization, graph-computations, algorithmic learning, computational geometry, etc.

• Discrepancy theory and computational geometry.- Dynamic motion planning in low obstacle density environments.- Visibility-based pursuit-evasion in a polygonal environment.- Maintaining the extent of a moving point set.- Finding cores of limited length.- On bipartite crossings, largest biplanar subgraphs, and the linear arrangement problem.- Approximation algorithms for a genetic diagnostics problem.- Cartographic line simplication and polygon CSG formulae in O(n log* n) time.- Constrained TSP and low-power computing.- On-line load balancing for related machines.- A linear-time algorithm for the 1-mismatch problem.- On some geometric optimization problems in layered manufacturing.- New TSP construction heuristics and their relationships to the 2-opt.- Pattern matching in hypertext.- Multiple approximate string matching.- Applied computational geometry - Abstract.- Checking the convexity of polytopes and the planarity of subdivisions (extended abstract).- Voronoi diagrams for polygon-offset distance functions.- Randomized algorithms for that ancient scheduling problem.- Optimal parallel algorithms for proximate points, with applications.- An efficient algorithm for shortest paths in vertical and horizontal segments.- On geometric path query problems.- On-line scheduling with hard deadlines.- Load balanced mapping of data structures in parallel memory modules for fast and conflict-free templates access.- Parallel vs. parametric complexity.- Position-independent near optimal searching and on-line recognition in star polygons.- Dynamic data structures for fat objects and their applications.- Intractability of assembly sequencing: Unit disks in the plane.- On hamiltonian triangulations in simple polygons (Extended Abstract).- Computing orthogonal drawings with the minimum number of bends.- On a simple depth-first search strategy for exploring unknown graphs.- Orthogonal drawing of high degree graphs with small area and few bends.- A centroid labelling technique and its application to path selection in trees.- Offset-polygon annulus placement problems.- Computing constrained minimum-width annuli of point sets.- Geometric Applications of Posets.- Constructing pairwise disjoint paths with few links.- Trans-dichotomous algorithms without multiplication - some upper and lower bounds.- An approximation algorithm for stacking up bins from a conveyer onto pallets.- Relaxed balance through standard rotations.- Efficient breakout routing in printed circuit boards.- Planarity, revisited (extended abstract).
• (source: Nielsen Book Data)

This book constitutes the refereed proceedings of the 5th International Workshop on Algorithms and Data Structures, WADS'97, held in Nova Scotia, Halifax, Canada, in August 1997. The 37 revised full papers presented were carefully selected from a total of 81 submissions. Also included are four abstracts and one full contribution corresponding to the invited talks. Among the topics covered are data structures and algorithmic aspects in a variety of areas like computational geometry, graph theory, networking, load balancing, optimization, approximation, sorting, pattern matching, etc.
(source: Nielsen Book Data)

• An improved pattern matching algorithm for strings in terms of straight-line programs.- Episode matching.- Efficient algorithms for approximate string matching with swaps.- On the complexity of pattern matching for highly compressed two-dimensional texts.- Estimating the probability of approximate matches.- Space- and time-efficient decoding with canonical huffman trees.- On weak circular squares in binary words.- An easy case of sorting by reversals.- External inverse pattern matching.- Distributed generation of suffix arrays.- Direct construction of compact directed acyclic word graphs.- Approximation algorithms for the fixed-topology phylogenetic number problem.- A new algorithm for the ordered tree inclusion problem.- On incremental computation of transitive closure and greedy alignment.- Aligning coding DNA in the presence of frame-shift errors.- A filter method for the weighted local similarity search problem.- Trie-based data structures for sequence assembly.- Flexible identification of structural objects in nucleic acid sequences: Palindromes, mirror repeats, pseudoknots and triple helices.- Banishing bias from consensus sequences.- On the Nadeau-Taylor theory of conserved chromosome segments.- Iterative versus simultaneous multiple sequence alignment.- Modern comparative lexicostatistics.
• (source: Nielsen Book Data)

This book constitutes the refereed proceedings of the Eighth Annual Symposium on Combinatorial Pattern Matching, CPM 97, held in Aarhus, Denmark, in June/July 1997. The volume presents 20 revised full papers carefully selected from 32 submissions received; also included are abstracts of two invited contributions. The volume is devoted to the issue of searching and matching strings and more complicated patterns, such as trees, regular expressions, graphs, point sets and arrays. The results presented are particularly relevant to molecular biology, but also to information retrieval, pattern recognition, compiling, data compression and program analysis.
(source: Nielsen Book Data)

• Invited Lectures
• External Memory Algorithms
• Design and Analysis of Dynamic Processes: A Stochastic Approach (Invited Paper)
• Data Structures
• Car-Pooling as a Data Structuring Device: The Soft Heap
• Optimal Prefix-Free Codes for Unequal Letter Costs: Dynamic Programming with the Monge Property
• Finding All the Best Swaps of a Minimum Diameter Spanning Tree Under Transient Edge Failures
• Strings and Biology
• Augmenting Suffix Trees, with Applications
• Longest Common Subsequence from Fragments via Sparse Dynamic Programming
• Computing the Edit-Distance Between Unrooted Ordered Trees
• Analogs and Duals of the MAST Problem for Sequences and Trees
• Numerical Algorithms
• Complexity Estimates Depending on Condition and Round-Off Error
• Intrinsic Near Quadratic Complexity Bounds for Real Multivariate Root Counting
• Fast Algorithms for Linear Algebra Modulo N
• A Probabilistic Zero-Test for Expressions Involving Roots of Rational Numbers
• Geometry
• Geometric Searching in Walkthrough Animations with Weak Spanners in Real Time
• A Robust Region Approach to the Computation of Geometric Graphs (Extended Abstract)
• Positioning Guards at Fixed Height Above a Terrain
• An Optimum Inapproximability Result
• Two-Center Problems for a Convex Polygon (Extended Abstract)
• Constructing Binary Space Partitions for Orthogonal Rectangles in Practice
• Randomized and On-Line Algorithms
• A Fast Random Greedy Algorithm for the Component Commonality Problem
• Maximizing Job Completions Online
• A Randomized Algorithm for Two Servers on the Line (Extended Abstract)
• Parallel and Distributed Algorithms I
• On Nonblocking Properties of the Beneš Network
• Adaptability and the Usefulness of Hints (Extended Abstract)
• Fault-Tolerant Broadcasting in Radio Networks (Extended Abstract)
• New Bounds for Oblivious Mesh Routing
• Evaluating Server-Assisted Cache Replacement in the Web
• Graph Algorithms
• Fully Dynamic Shortest Paths and Negative Cycles Detection on Digraphs with Arbitrary Arc Weights
• A Functional Approach to External Graph Algorithms
• Minimal Triangulations for Graphs with "Few" Minimal Separators
• Finding an Optimal Path without Growing the Tree
• An Experimental Study of Dynamic Algorithms for Directed Graphs
• Matching Medical Students to Pairs of Hospitals: A New Variation on a Well-known Theme
• Parallel and Distributed Algorithms II --?-Stepping : A Parallel Single Source Shortest Path Algorithm
• Improved Deterministic Parallel Padded Sorting
• Analyzing an Infinite Parallel Job Allocation Process
• Nearest Neighbor Load Balancing on Graphs
• Optimization
• 2-Approximation Algorithm for Finding a Spanning Tree with Maximum Number of Leaves
• Moving-Target TSP and Related Problems
• Fitting Points on the Real Line and Its Application to RH Mapping
• Approximate Coloring of Uniform Hypergraphs (Extended Abstract)
• Techniques for Scheduling with Rejection
• Computer-Aided Way to Prove Theorems in Scheduling.

This book constitutes the refereed proceedings of the 6th Annual European Symposium on Algorithms, ESA'97, held in Venice, Italy, in August 1998. The 40 revised full papers presented together with two invited contributions were carefully reviewed and selected from a total of 131 submissions. The book is divided into sections on data structures, strings and biology, numerical algorithms, geometry, randomized and online algorithms, parallel and distributed algorithms, graph algorithms, and optimization.