In the last thirty years, combinatorial mathematics has found itself at the heart of many technological applications. The aims of the conference on which this book is based were to stimulate combinatorial mathematicians to pursue new lines of research of potential and practical importance, and to uncover the breadth of applications to the subject. Topics covered include neural networks, cryptography, radio frequency assignment for mobile telecommunications, coding theory, sequences for communications applications, interconnection networks, data types, knot theory, radar, parallel processing, network reliability, formal specification of programs and protocols, and combinatorial optimization.

This book is a study of combinatorial structures of 3-mani- folds, especially Haken 3-manifolds. Specifically, it is concerned with Heegard graphs in Haken 3-manifolds, i.e., with graphs whose complements have a free fundamental group. These graphs always exist. They fix not only a combinatorial stucture but also a presentation for the fundamental group of the underlying 3-manifold. The starting point of the book is the result that the intersection of Heegard graphs with incompressible surfaces, or hierarchies of such surfaces, is very rigid. A number of finiteness results lead up to a ri- gidity theorem for Heegard graphs. The book is intended for graduate students and researchers in low-dimensional topolo- gy as well as combinatorial theory. It is self-contained and requires only a basic knowledge of the theory of 3-manifolds

This book provides an up-to-date and rapid introduction to an important and currently active topic in graph theory. The author leads the reader to the forefront of research in this area. Complete and easily readable proofs of all the main theorems, together with numerous examples, exercises and open problems are given. The book is suitable for use as a textbook or as seminar material for advanced undergraduate and graduate students. The references are comprehensive and so it will also be useful for researchers as a handbook.

This book presents a collection of 33 strictly refereed full papers on combinatorics and computer science; these papers have been selected from the 54 papers accepted for presentation at the joint 8th Franco-Japanese and 4th Franco-Chinese Conference on Combinatorics in Computer Science, CCS '96, held in Brest, France in July 1995.
The papers included in the book have been contributed by authors from 10 countries; they are organized in sections entitled graph theory, combinatorial optimization, selected topics, and parallel and distributed computing.

This volume presents the proceedings of the 20th International Workshop on Graph-Theoretic Concepts in Computer Science (WG '94), held in Herrsching, Germany in June 1994.
The volume contains 32 thoroughly revised papers selected from 66 submissions and provides an up-to-date snapshot of the research performed in the field. The topics addressed are graph grammars, treewidth, special graph classes, algorithms on graphs, broadcasting and architecture, planar graphs and related problems, and special graph problems.

The first part of this text covers the main graph theoretic topics: connectivity, trees, traversability, planarity, colouring, covering, matching, digraphs, networks, matrices of a graph, graph theoretic algorithms, and matroids. These concepts are then applied in the second part to problems in engineering, operations research, and science as well as to an interesting set of miscellaneous problems, thus illustrating their broad applicability. Every effort has been made to present applications that use not merely the notation and terminology of graph theory, but also its actual mathematical results. Some of the applications, such as in molecular evolution, facilities layout, and graffic network design, have never appeared before in book form. Written at an advanced undergraduate to beginning graduate level, this book is suitable for students of mathematics, engineering, operations research, computer science, and physical sciences as well as for researchers and practitioners with an interest in graph theoretic modelling.

This volume constitutes the proceedings of the DIMACS International Workshop on Graph Drawing, GD '94, held in Princeton, New Jersey in October 1994.
The 50 papers and system descriptions presented address the problem of constructing geometric representations of abstract graphs, networks and hypergraphs, with applications to key technologies such as software engineering, databases, visual interfaces, and circuit layout; they are organized in sections on three-dimensional drawings, orthogonal drawings, planar drawings, crossings, applications and systems, geometry, system demonstrations, upward drawings, proximity drawings, declarative and other approaches; in addition reports on a graph drawing contest and a poster gallery are included.

This book contains a collection of 37 refereed full papers selected from the contributions presented at the 5th International Workshop on Graph Grammars and Their Applications to Computer Science, held in Williamsburg, Virginia, USA, in November 1994.
The book covers the whole spectrum of methods and techniques for the investigation of the structure of graphs and graph transformations. The papers are divided into nine topical sections on rewriting techniques, specification and semantics, software engineering, algorithms and architectures, concurrency, graph languages, pattern and graphics, structure and logic of graphs, and biology.

This book constitutes the refereed proceedings of the 7th Annual Symposium on Combinatorial Pattern Matching, CPM '96, held in Laguna Beach, California, USA, in June 1996.
The 26 revised full papers included were selected from a total of 48 submissions; also included are two invited papers. Combinatorial pattern matching has become a full-fledged area of algorithmics with important applications in recent years.
The book addresses all relevant aspects of combinatorial pattern matching and its importance in information retrieval, pattern recognition, compiling, data compression, program analysis, and molecular biology and thus describes the state of the art in the area.

This introduction to most of the classical concepts of pure and applied graph theory covers many of the major classical theorems. The emphasis is on algorithms and their complexity--what graph problems have known efficient solutions and which are intractable.

The journal aequationes mathematicae publishes papers in pure and applied mathematics and, in particular, articles on functional equations, combinatorics and dynamical systems. Its 50th volume appears in 1995. To mark this occasion, we are publishing in book form a repre- sentative collection of outstanding survey papers assembled for our anniversary issue of aequationes mathematicae. The articles by Quackenbush, Targonski and Moszner discuss composition of functions from different points of view: universal algebra, dynamical systems (iteration) and functional equa- tions. The Ono-Robbins-Wahl and the Vince papers, on number theory and tiles, respectively, are thematically linked by lattices. Combinatorics, in turn, links the Vince paper with that of Tutte, whose subject is chromatic sums, its tools differential and functional equations. The Paganoni-Ratz and the Forti papers deal with conditional functional equations and with the related topic of stability. Applications to the social and behavioral sciences, in particular to aggregation (and some theory) are presented in the paper by J. Aczel. The aim of the collection is to survey selected fields of current interest. We trust that it will be useful and informative for researchers, teachers, graduate and advanced undergraduate stu- dents of mathematics, and for those interested in applications in related fields. lanDs Aczel Aequationes Mathematicae 50 (1995) 1 0001-9054/95/020001-01 $1.50 + 0.20/0 University of Waterloo (c) 1995 Birkhiiuser Verlag, Basel Editorial Volume 50 of Aequationes Mathematicae This is the fiftieth volume of aequationes mathematicae. Not only our modesty but also lack of space keeps us from self-congratulation.

Still today I am receiving requests for reprints of the book, but unfortunately it is out of print. Therefore, since the book still seems to receive some attention, I p- posed to Springer Verlag to provide a free online edition. I am very happy that Springer agreed. Except for the correction of some typographical errors, the online edition is just a copy of the printed version, no updates have been made. In particular, Table 13.1 gives the status of TSPLIB at the time of publishing the book. For accessing TSPLIB the link http://www.iwr.uni-heidelberg.de/iwr/comopt/software/TSPLIB95/ should be used instead of following the procedure described in Chapter 13. Heidelberg, January 2001 Gerhard Reinelt Preface More than ?fteen years ago, I was faced with the following problem in an assignment for a class in computer science. A brewery had to deliver beer to ?ve stores, and the task was to write a computer program for determining the shortest route for the truck driver to visit all stores and return to the brewery. All my attemps to ?nd a reasonable algorithm failed, I could not help enumerating all possible routes and then select the best one.

This volume presents the proceedings of the Fifth Annual Symposium on Combinatorial Pattern Matching, held at Asilomar, California, in June 1994. The 26 selected papers in this volume are organized in chapters on Alignments, Various Matchings, Combinatorial Aspects, and Bio-Informatics. Combinatorial Pattern Matching addresses issues of searching and matching of strings and more complicated patterns, as for example trees. The goal is to derive non-trivial combinatorial properties for such structures and then to exploit these properties in order to achieve superior performance for the corresponding computational problems. In recent years, combinatorial pattern matching has developed into a full-fledged area of algorithmics and is expected to grow even further during the next years.

This volume contains the proceedings of the 19th International Workshop on Graph-Theoretic Concepts in Computer Science, WG '93, held near Utrecht, The Netherlands, in 1993.
The papers are grouped into parts on: hard problems on classes of graphs, structural graph theory, dynamic graph algorithms, structure-oriented graph algorithms, graph coloring, AT-free and chordal graphs, circuits and nets, graphs and interconnection networks, routing and shortest paths, and graph embedding and layout.
The 35 revised papers were chosen from 92 submissions after a careful refereeing process.

This book constitutes the proceedings of the First Annual International Conference on Computing and Combinatorics, COCOON '95, held in Xi'an, China in August 1995.
The 52 thoroughly refereed full papers and the 22 short presentations included in this volume were selected from a total of 120 submissions. All current aspects of theoretical computer science and combinatorial mathematics related to computing are addressed; in particular, there are sections on complexity theory, graph drawing, computational geometry, databases, graph algorithms, distributed programming and logic, combinatorics, machine models, combinatorial designs, algorithmic learning, algorithms, distributed computing, and scheduling.

CONTENTS: D.D. Dawson: Measure-valued Markov Processes.- B. Maisonneuve: Processus de Markov: Naissance, Retournement, Regeneration.- J. Spencer: Nine lectures on Random Graphs

One of the most powerful ways to understand data is to recognize the ways in which each datum-person, product, etc-connects to another. Visualizing these graphs makes it possible to literally see the connections. The graph model consists of data elements, called nodes, and edges, which are the relationships between these nodes. Graphs make the relationships between the data elements a core part of the data structure, which means you can better comprehend the meaning of your data. And visual data is easier for everyone to understand. Visualizing Graph Data teaches readers not only how to build graph data structures, but also how to create their own dynamic, interactive visualizations using a variety of tools. This book is loaded with fascinating examples and case studies to show the real-world value of graph visualizations. It begins by teaching fundamental graph concepts and techniques used to visualize graph data. Next, readers drill down to learn how to create their own useful visualizations, as well as additional tools. Readers also learn how to model data, create the best graphs for their particular audience, handle big data, and depict temporal and spatial data. By the end of this book, readers know to ask the right questions of data to create powerful visualizations. Key Features: * Real-world case studies * Teaches techniques for creating effective visualizations * Shows fundamental visualization concepts * Includes tutorials using the best visualization tools AUDIENCE A basic understanding of RDBMS systems is assumed. No previous knowledge of graph databases required. ABOUT THE TECHNOLOGY The graph way of thinking about data is becoming more and more popular as people value the relationships between bits of data as much as the data themselves. Key to understanding the complex structure of connected data is being able to visualize those connections.

This volume contains the 22 papers accepted for presentation at the Third Annual Symposium on Combinatorial Pattern Matching held April 29 to May 1, 1992, in Tucson, Arizona; it constitutes the first conference proceedings entirely devoted to combinatorial pattern matching (CPM). CPM deals withissues of searching and matching of strings and other more complicated patterns such as trees, regular expressions, extended expressions, etc. in order to derive combinatorial properties for such structures. As an interdisciplinary field of growing interest, CPM is related to research in information retrieval, pattern recognition, compilers, data compression, and program analysis as well as to results, problems and methods from combinatorial mathematics and molecular biology.

Combinatorial group theory is a loosely defined subject, with close connections to topology and logic. With surprising frequency, problems in a wide variety of disciplines, including differential equations, automorphic functions and geometry, have been distilled into explicit questions about groups, typically of the following kind: Are the groups in a given class finite (e.g., the Burnside problem)? Finitely generated? Finitely presented? What are the conjugates of a given element in a given group? What are the subgroups of that group? Is there an algorithm for deciding for every pair of groups in a given class whether they are isomorphic or not? The objective of combinatorial group theory is the systematic development of algebraic techniques to settle such questions. In view of the scope of the subject and the extraordinary variety of groups involved, it is not surprising that no really general theory exists. These notes, bridging the very beginning of the theory to new results and developments, are devoted to a number of topics in combinatorial group theory and serve as an introduction to the subject on the graduate level.

This book is about orthomorphisms and complete mappings of groups, and related constructions of orthogonal latin squares. It brings together, for the first time in book form, many of the results in this area. The aim of this book is to lay the foundations for a theory of orthomorphism graphsof groups, and to encourage research in this area. To this end, many directions for future research are suggested. The material in this book should be accessible to any graduate student who has taken courses in algebra (group theory and field theory). It will mainly be useful in research on combinatorial design theory, group theory and field theory.

In February 1992, I defended my doctoral thesis: Engineering Optimiza tion - selected contributions (IMSOR, The Technical University of Den mark, 1992, p. 92). This dissertation presents retrospectively my central contributions to the theoretical and applied aspects of optimization. When I had finished my thesis I became interested in editing a volume related to a new expanding area of applied optimization. I considered several approaches: simulated annealing, tabu search, genetic algorithms, neural networks, heuristics, expert systems, generalized multipliers, etc. Finally, I decided to edit a volume related to simulated annealing. My main three reasons for this choice were the following: (i) During the last four years my colleagues at IMSOR and I have car ried out several applied projects where simulated annealing was an essential. element in the problem-solving process. Most of the avail able reports and papers have been written in Danish. After a short review I was convinced that most of these works deserved to be pub lished for a wider audience. (ii) After the first reported applications of simulated annealing (1983- 1985), a tremendous amount of theoretical and applied work have been published within many different disciplines. Thus, I believe that simulated annealing is an approach that deserves to be in the curricula of, e.g. Engineering, Physics, Operations Research, Math ematical Programming, Economics, System Sciences, etc. (iii) A contact to an international network of well-known researchers showed that several individuals were willing to contribute to such a volume."

This book principally concerns the rapidly growing area of what might be termed "Logical Complexity Theory": the study of bounded arithmetic, propositional proof systems, length of proof, and similar themes, and the relations of these topics to computational complexity theory. Issuing from a two-year international collaboration, the book contains articles concerning the existence of the most general unifier, a special case of Kreisel's conjecture on length-of-proof, propositional logic proof size, a new alternating logtime algorithm for boolean formula evaluation and relation to branching programs, interpretability between fragments of arithmetic, feasible interpretability, provability logic, open induction, Herbrand-type theorems, isomorphism between first and second order bounded arithmetics, forcing techniques in bounded arithmetic, and ordinal arithmetic in *L *D o. Also included is an extended abstract of J.P. Ressayre's new approach concerning the model completeness of the theory of real closed exponential fields. Additional features of the book include the transcription and translation of a recently discovered 1956 letter from Kurt Godel to J. von Neumann, asking about a polynomial time algorithm for the proof in k-symbols of predicate calculus formulas (equivalent to the P-NP question); and an open problem list consisting of seven fundamental and 39 technical questions contributed by many researchers, together with a bibliography of relevant references. This scholarly work will interest mathematical logicians, proof and recursion theorists, and researchers in computational complexity.

This is the first-ever book on computational group theory. It provides extensive and up-to-date coverage of the fundamental algorithms for permutation groups with reference to aspects of combinatorial group theory, soluble groups, and p-groups where appropriate. The book begins with a constructive introduction to group theory and algorithms for computing with small groups, followed by a gradual discussion of the basic ideas of Sims for computing with very large permutation groups, and concludes with algorithms that use group homomorphisms, as in the computation of Sylowsubgroups. No background in group theory is assumed. The emphasis is on the details of the data structures and implementation which makes the algorithms effective when applied to realistic problems. The algorithms are developed hand-in-hand with the theoretical and practical justification.All algorithms are clearly described, examples are given, exercises reinforce understanding, and detailed bibliographical remarks explain the history and context of the work. Much of the later material on homomorphisms, Sylow subgroups, and soluble permutation groups is new.

One way to advance the science of computational geometry is to make a comprehensive study of fundamental operations that are used in many different algorithms. This monograph attempts such an investigation in the case of two basic predicates: the counterclockwise relation pqr, which states that the circle through points (p, q, r) is traversed counterclockwise when we encounter the points in cyclic order p, q, r, p, ...; and the incircle relation pqrs, which states that s lies inside that circle if pqr is true, or outside that circle if pqr is false. The author, Donald Knuth, is one of the greatest computer scientists of our time. A few years ago, he and some of his students were looking at amap that pinpointed the locations of about 100 cities. They asked, "Which ofthese cities are neighbors of each other?" They knew intuitively that some pairs of cities were neighbors and some were not; they wanted to find a formal mathematical characterization that would match their intuition.This monograph is the result.

An effort has been made to present the various topics in the theory of graphs in a logical order, to indicate the historical background, and to clarify the exposition by including figures to illustrate concepts and results. In addition, there are three appendices which provide diagrams of graphs, directed graphs, and trees. The emphasis throughout is on theorems rather than algorithms or applications, which however are occaisionally mentioned.