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.

This volume comprises 17 contributions that present advanced topics in graph domination, featuring open problems, modern techniques, and recent results. The book is divided into 3 parts. The first part focuses on several domination-related concepts: broadcast domination, alliances, domatic numbers, dominator colorings, irredundance in graphs, private neighbor concepts, game domination, varieties of Roman domination and spectral graph theory. The second part covers domination in hypergraphs, chessboards, and digraphs and tournaments. The third part focuses on the development of algorithms and complexity of signed, minus and majority domination, power domination, and alliances in graphs. The third part also includes a chapter on self-stabilizing algorithms. Of extra benefit to the reader, the first chapter includes a glossary of commonly used terms. The book is intended to provide a reference for established researchers in the fields of domination and graph theory and graduate students who wish to gain knowledge of the topics covered as well as an overview of the major accomplishments and proof techniques used in the field.

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 introduction to the theory of rigid structures explains how to analyze the performance of built and natural structures under loads, paying special attention to the role of geometry. The book unifies the engineering and mathematical literatures by exploring different notions of rigidity - local, global, and universal - and how they are interrelated. Important results are stated formally, but also clarified with a wide range of revealing examples. An important generalization is to tensegrities, where fixed distances are replaced with 'cables' not allowed to increase in length and 'struts' not allowed to decrease in length. A special feature is the analysis of symmetric tensegrities, where the symmetry of the structure is used to simplify matters and allows the theory of group representations to be applied. Written for researchers and graduate students in structural engineering and mathematics, this work is also of interest to computer scientists and physicists.

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.

This book presents a selection of the papers presented at EUROCODE '90, the symposium on coding theory held in Udine, Italy, November 1990. It gives the state of the art on coding in Europe and ranges from theoretical top- ics like algebraic geometry and combinatorial coding to applications like modulation, real-space decoding and VLSI implementation. The book is divided into eight sections: - Algebraic codes - Combinatorial codes - Geometric codes - Protection of information - Convolutional codes - Information theory - Modulation - Applications of coding. Five of the sections are introduced by an invited contribution.

The AAECC conferences focus on the algebraic aspects of modern computer science, which includes the most up-to-date and advanced topics. The topic of error-correcting codes is one where theory and implementation are unifiedinto a subject both of mathematical beauty and of practical importance. Algebraic algorithms are not only interesting theoretically but also important in computer and communication engineering and many other fields. This volume contains the proceedings of the 9th AAECC conference, held in New Orleans, LA, in October 1991. Researchers from Europe, America, Japan and other regions of the world presented papers at the conference. The papers present new results of recent theoretical and application-oriented research in the field.

These proceedings reflect the main activities of the Paris S minaire d'Alg bre 1989-1990, with a series of papers in Invariant Theory, Representation Theory and Combinatorics. It contains original works from J. Dixmier, F. Dumas, D. Krob, P. Pragacz and B.J. Schmid, as well as a new presentation of Derived Categories by J.E. Bj rk and as introduction to the deformation theory of Lie equations by J.F. Pommaret. J. Dixmier: Sur les invariants du groupe sym trique dans certaines repr sentations II.- B.J. Schmid: Finite groups and invariant theory.- J.E. Bj rk: Derived categories.- P. Pragacz: Algebro-Geometric applications of Schur S- and Q-polynomials.- F. Dumas: Sous-corps de fractions rationnelles des corps gauches de s ries de Laurent.- D. Krob: Expressions rationnelles sur un anneau.- J.F. Pommaret: Deformation theory of algebraic and Geometric structures.- M. van den Bergh: Differential operators on semi-invariants for tori and weighted projective spaces.

Parallelism or concurrency is one of the fundamental concepts in computer science. But in spite of its importance, theoretical methods to handle concurrency are not yet sufficiently developed. This volume presents a comprehensive study of Mazurkiewicz' trace theory from an algebraic-combinatorial point of view. This theory is recognized as an important tool for a rigorous mathematical treatment of concurrent systems. The volume covers several different research areas, and contains not only known results but also various new results published nowhere else. Chapter 1 introduces basic concepts. Chapter 2 gives a straight path to Ochmanski's characterization of recognizable trace languages and to Zielonka's theory of asynchronous automata. Chapter 3 applies the theory of traces to Petri nets. A kind of morphism between nets is introduced which generalizes the concept of synchronization. Chapter 4 provides a new bridge between the theory of string rewriting and formal power series. Chapter 5 is an introduction to a combinatorial theory of rewriting on traces which can be used as an abstract calculus for transforming concurrent processes.

The fields of integer programming and combinatorial optimization continue to be areas of great vitality, with an ever increasing number of publications and journals appearing. A classified bibliography thus continues to be necessary and useful today, even more so than it did when the project, of which this is the fifth volume, was started in 1970 in the Institut fur Okonometrie und Operations Research of the University of Bonn. The pioneering first volume was compiled by Claus Kastning during the years 1970 - 1975 and appeared in 1976 as Volume 128 of the series Lecture Notes in Economics and Mathematical Systems published by the Springer Verlag. Work on the project was continued by Dirk Hausmann, Reinhardt Euler, and Rabe von Randow, and resulted in the publication of the second, third, and fourth volumes in 1978, 1982, and 1985 (Volumes 160, 197, and 243 of the above series). The present book constitutes the fifth volume of the bibliography and covers the period from autumn 1984 to the end of 1987. It contains 5864 new publications by 4480 authors and was compiled by Rabe von Randow. Its form is practically identical to that of the first four volumes, some additions having been made to the subject list.

The central theme of this volume is commutative algebra, with emphasis on special graded algebras, which are increasingly of interest in problems of algebraic geometry, combinatorics and computer algebra. Most of the papers have partly survey character, but are research-oriented, aiming at classification and structural results.

This volume presents papers from the 2nd Scandinavian Workshop on Algorithm Theory. The contributions describe original research on algorithms and data structures, in all areas, including combinatorics, computational geometry, parallel computing, and graph theory. The majority of the papers focus on the design and complexity analysis of: data structures, text algorithms, and sequential and parallel algorithms for graph problems and for geometric problems. Examples of tech- niques presented include: - efficient ways to find approximation algorithms for the maximum independent set problem and for graph coloring; - exact estimation of the expected search cost for skip lists; - construction of canonical representations of partial 2-trees and partial 3-trees in linear time; - efficient triangulation of planar point sets and convex polygons.