The huge bandwidth of optical fiber was recognized back in the 1970s during the early development of fiber optic technology. For the last two decades, the capacity of experimental and deployed systems has been increasing at a rate of 100-fold each decade-a rate exceeding the increase of integrated circuit speeds. Today, optical communication in the public communication networks has developed from the status of a curiosity into being the dominant technology. Various great challenges arising from the deployment of the wavelength division multiplexing (WDM) have attracted a lot of efforts from many researchers. Indeed, the optical networking has been a fertile ground for both theoretical researches and experimental studies. This monograph presents the contribution from my past and ongoing research in the optical networking area. The works presented in this book focus more on graph-theoretical and algorithmic aspects of optical networks. Although this book is limited to the works by myself and my coauthors, there are many outstanding achievements made by other individuals, which will be cited in many places in this book. Without the inspiration from their efforts, this book would have never been possible. This monograph is divided into four parts: * Multichannel Optical Networking Architectures, * Broadcast-and-Select Passive Optical Networks, * Wavelength-Switched Optical Networks, * SONET/WDM Optical Networks. The first part consists of the first three chapters. Chapter 1 pro vides a brief survey on the networking architectures of optical trans- XVll xvm MULTICHANNEL OPTICAL NETWORKS port networks, optical access networks and optical premise networks.

This book constitutes the refereed proceedings of the 13th European Conference on Evolutionary Computation in Combinatorial Optimization, EvoCOP 2013, held in Vienna, Austria, in April 2013, colocated with the Evo* 2013 events EuroGP, EvoBIO, EvoMUSART, and EvoApplications. The 23 revised full papers presented were carefully reviewed and selected from 50 submissions. The papers present the latest research and discuss current developments and applications in metaheuristics - a paradigm to effectively solve difficult combinatorial optimization problems appearing in various industrial, economic, and scientific domains. Prominent examples of metaheuristics are ant colony optimization, evolutionary algorithms, greedy randomized adaptive search procedures, iterated local search, simulated annealing, tabu search, and variable neighborhood search. Applications include scheduling, timetabling, network design, transportation and distribution, vehicle routing, the travelling salesman problem, packing and cutting, satisfiability, and general mixed integer programming.

This book presents novel graph-theoretic methods for complex computer vision and pattern recognition tasks. It presents the application of graph theory to low-level processing of digital images, presents graph-theoretic learning algorithms for high-level computer vision and pattern recognition applications, and provides detailed descriptions of several applications of graph-based methods to real-world pattern recognition tasks.

In the spectrum of mathematics, graph theory which studies a mathe matical structure on a set of elements with a binary relation, as a recognized discipline, is a relative newcomer. In recent three decades the exciting and rapidly growing area of the subject abounds with new mathematical devel opments and significant applications to real-world problems. More and more colleges and universities have made it a required course for the senior or the beginning postgraduate students who are majoring in mathematics, computer science, electronics, scientific management and others. This book provides an introduction to graph theory for these students. The richness of theory and the wideness of applications make it impossi ble to include all topics in graph theory in a textbook for one semester. All materials presented in this book, however, I believe, are the most classical, fundamental, interesting and important. The method we deal with the mate rials is to particularly lay stress on digraphs, regarding undirected graphs as their special cases. My own experience from teaching out of the subject more than ten years at University of Science and Technology of China (USTC) shows that this treatment makes hardly the course di: fficult, but much more accords with the essence and the development trend of the subject."

At first sight discrete and fractional programming techniques appear to be two com pletely unrelated fields in operations research. We will show how techniques in both fields can be applied separately and in a combined form to particular models in location analysis. Location analysis deals with the problem of deciding where to locate facilities, con sidering the clients to be served, in such a way that a certain criterion is optimized. The term "facilities" immediately suggests factories, warehouses, schools, etc., while the term "clients" refers to depots, retail units, students, etc. Three basic classes can be identified in location analysis: continuous location, network location and dis crete location. The differences between these fields arise from the structure of the set of possible locations for the facilities. Hence, locating facilities in the plane or in another continuous space corresponds to a continuous location model while finding optimal facility locations on the edges or vertices of a network corresponds to a net work location model. Finally, if the possible set of locations is a finite set of points we have a discrete location model. Each of these fields has been actively studied, arousing intense discussion on the advantages and disadvantages of each of them. The usual requirement that every point in the plane or on the network must be a candidate location point, is one of the mostly used arguments "against" continuous and network location models."

This book shows how the Bayesian Approach (BA) improves well known heuristics by randomizing and optimizing their parameters. That is the Bayesian Heuristic Approach (BHA). The ten in-depth examples are designed to teach Operations Research using Internet. Each example is a simple representation of some impor tant family of real-life problems. The accompanying software can be run by remote Internet users. The supporting web-sites include software for Java, C++, and other lan guages. A theoretical setting is described in which one can discuss a Bayesian adaptive choice of heuristics for discrete and global optimization prob lems. The techniques are evaluated in the spirit of the average rather than the worst case analysis. In this context, "heuristics" are understood to be an expert opinion defining how to solve a family of problems of dis crete or global optimization. The term "Bayesian Heuristic Approach" means that one defines a set of heuristics and fixes some prior distribu tion on the results obtained. By applying BHA one is looking for the heuristic that reduces the average deviation from the global optimum. The theoretical discussions serve as an introduction to examples that are the main part of the book. All the examples are interconnected. Dif ferent examples illustrate different points of the general subject. How ever, one can consider each example separately, too."

This is the first book devoted to the systematic study of sparse graphs and sparse finite structures. Although the notion of sparsity appears in various contexts and is a typical example of a hard to define notion, the authors devised an unifying classification of general classes of structures. This approach is very robust and it has many remarkable properties. For example the classification is expressible in many different ways involving most extremal combinatorial invariants. This study of sparse structures found applications in such diverse areas as algorithmic graph theory, complexity of algorithms, property testing, descriptive complexity and mathematical logic (homomorphism preservation,fixed parameter tractability and constraint satisfaction problems). It should be stressed that despite of its generality this approach leads to linear (and nearly linear) algorithms. Jaroslav Nesetril is a professor at Charles University, Prague; Patrice Ossona de Mendez is a CNRS researcher et EHESS, Paris. This book is related to the material presented by the first author at ICM 2010.

Certain constrained combinatorial optimization problems have a natural analogue in the continuous setting of the classical isoperimetric problem. The study of so called combinatorial isoperimetric problems exploits similarities between these two, seemingly disparate, settings. This text focuses on global methods. This means that morphisms, typically arising from symmetry or direct product decomposition, are employed to transform new problems into more restricted and easily solvable settings whilst preserving essential structure. This book is based on Professor Harper's many years' experience in teaching this subject and is ideal for graduate students entering the field. The author has increased the utility of the text for teaching by including worked examples, exercises and material about applications to computer science. Applied systematically, the global point of view can lead to surprising insights and results, and established researchers will find this to be a valuable reference work on an innovative method for problem solving.

This work contains the proceedings of the "Mathematics and Culture" conference held in Venice in March 2002. The conference aims to act as a bridge across the various aspects of human knowledge. While keeping mathematics as its core, it is aimed at anyone endowed with cultural curiosity and interests, whether within or (even more so) outside mathematics. This volume therefore covers music, cinema, art, theatre and literature, with topics ranging from Tibet to comics.

Topics in Matroid Theory provides a brief introduction to matroid theory with an emphasis on algorithmic consequences.Matroid theory is at the heart of combinatorial optimization and has attracted various pioneers such as Edmonds, Tutte, Cunningham and Lawler among others. Matroid theory encompasses matrices, graphs and other combinatorial entities under a common, solid algebraicframework, thereby providing the analytical tools to solve related difficult algorithmic problems. The monograph contains a rigorousaxiomatic definition of matroids along with other necessary concepts such as duality, minors, connectivity and representability asdemonstrated in matrices, graphs and transversals. The author also presents a deep decomposition result in matroid theory that providesa structural characterization of graphic matroids, and show how this can be extended to signed-graphic matroids, as well as the immediatealgorithmic consequences.

"

The flood of information through various computer networks such as the In ternet characterizes the world situation in which we live. Information worlds, often called virtual spaces and cyberspaces, have been formed on computer networks. The complexity of information worlds has been increasing almost exponentially through the exponential growth of computer networks. Such nonlinearity in growth and in scope characterizes information worlds. In other words, the characterization of nonlinearity is the key to understanding, utiliz ing and living with the flood of information. The characterization approach is by characteristic points such as peaks, pits, and passes, according to the Morse theory. Another approach is by singularity signs such as folds and cusps. Atoms and molecules are the other fundamental characterization ap proach. Topology and geometry, including differential topology, serve as the framework for the characterization. Topological Modeling for Visualization is a textbook for those interested in this characterization, to understand what it is and how to do it. Understanding is the key to utilizing information worlds and to living with the changes in the real world. Writing this textbook required careful preparation by the authors. There are complex mathematical concepts that require designing a writing style that facilitates understanding and appeals to the reader. To evolve a style, we set as a main goal of this book the establishment of a link between the theoretical aspects of modern geometry and topology, on the one hand, and experimental computer geometry, on the other.

This volume contains the accounts of papers delivered at the Nato Advanced Study Institute on Finite and Infinite Combinatorics in Sets and Logic held at the Banff Centre, Alberta, Canada from April 21 to May 4, 1991. As the title suggests the meeting brought together workers interested in the interplay between finite and infinite combinatorics, set theory, graph theory and logic. It used to be that infinite set theory, finite combinatorics and logic could be viewed as quite separate and independent subjects. But more and more those disciplines grow together and become interdependent of each other with ever more problems and results appearing which concern all of those disciplines. I appreciate the financial support which was provided by the N. A. T. O. Advanced Study Institute programme, the Natural Sciences and Engineering Research Council of Canada and the Department of Mathematics and Statistics of the University of Calgary. 11l'te meeting on Finite and Infinite Combinatorics in Sets and Logic followed two other meetings on discrete mathematics held in Banff, the Symposium on Ordered Sets in 1981 and the Symposium on Graphs and Order in 1984. The growing inter-relation between the different areas in discrete mathematics is maybe best illustrated by the fact that many of the participants who were present at the previous meetings also attended this meeting on Finite and Infinite Combinatorics in Sets and Logic.

The Virasoro algebra is an infinite dimensional Lie algebra that plays an increasingly important role in mathematics and theoretical physics. This book describes some fundamental facts about the representation theory of the Virasoro algebra in a self-contained manner. Topics include the structure of Verma modules and Fock modules, the classification of (unitarizable) Harish-Chandra modules, tilting equivalence, and the rational vertex operator algebras associated to the so-called minimal series representations.

Covering a wide range of material, this book has three appendices which provide background information required for some of the chapters. The authors organize fundamental results in a unified way and refine existing proofs. For instance in chapter three, a generalization of Jantzen filtration is reformulated in an algebraic manner, and geometric interpretation is provided. Statements, widely believed to be true, are collated, and results which are known but not verified are proven, such as the corrected structure theorem of Fock modules in chapter eight.

This book will be of interest to a wide range of mathematicians and physicists from the level of graduate students to researchers.

I. The topics of this book The concept of a matroid has been known for more than five decades. Whitney (1935) introduced it as a common generalization of graphs and matrices. In the last two decades, it has become clear how important the concept is, for the following reasons: (1) Combinatorics (or discrete mathematics) was considered by many to be a collection of interesting, sometimes deep, but mostly unrelated ideas. However, like other branches of mathematics, combinatorics also encompasses some gen eral tools that can be learned and then applied, to various problems. Matroid theory is one of these tools. (2) Within combinatorics, the relative importance of algorithms has in creased with the spread of computers. Classical analysis did not even consider problems where "only" a finite number of cases were to be studied. Now such problems are not only considered, but their complexity is often analyzed in con siderable detail. Some questions of this type (for example, the determination of when the so called "greedy" algorithm is optimal) cannot even be answered without matroidal tools."

Mathematics and Computer Science III contains invited and contributed papers on combinatorics, random graphs and networks, algorithms analysis and trees, branching processes, constituting the Proceedings of the Third International Colloquium on Mathematics and Computer Science, held in Vienna in September 2004. It addresses a large public in applied mathematics, discrete mathematics and computer science, including researchers, teachers, graduate students and engineers.

The self-avoiding walk is a mathematical model that has important applications in statistical mechanics and polymer science. In spite of its simple definition a path on a lattice that does not visit the same site more than once it is difficult to analyze mathematically. "TheSelf-Avoiding Walk"provides the firstunified account of the known rigorous results for the self-avoiding walk, with particular emphasis on its critical behavior. Its goals are to give an account of the current mathematical understanding of the model, to indicate some of the applications of the concept in physics and in chemistry, and to give an introduction to some of the nonrigorous methods used in those fields.

Topics covered in the bookinclude: the lace expansion and its application to the self-avoiding walk in more than four dimensions where most issues are now resolved; an introduction to the nonrigorous scaling theory; classical work of Hammersley and others; a new exposition of Kesten s pattern theorem and its consequences; a discussion of the decay of the two-point function and its relation to probabilistic renewal theory; analysis of Monte Carlo methods that have been used to study the self-avoiding walk; the role of the self-avoiding walk in physical and chemical applications. Methods from combinatorics, probability theory, analysis, and mathematical physics play important roles. The book is highly accessible to both professionals and graduate students in mathematics, physics, and chemistry.

"

This uniquely authoritative and comprehensive handbook is the first to cover the vast field of formal languages, as well as its traditional and most recent applications to such diverse areas as linguistics, developmental biology, computer graphics, cryptology, molecular genetics, and programming languages. No other work comes even close to the scope of this one. The editors are extremely well-known theoretical computer scientists, and each individual topic is presented by the leading authorities in the particular field. The maturity of the field makes it possible to include a historical perspective in many presentations. The work is divided into three volumes, which may be purchased as a set.

Combinatorics as a branch of mathematics studies the arts of counting. Enumeration occupies the foundation of combinatorics with a large range of applications not only in mathematics itself but also in many other disciplines. It is too broad a task to write a book to show the deep development in every corner from this aspect. This monograph is intended to provide a unified theory for those related to the enumeration of maps. For enumerating maps the first thing we have to know is the sym metry of a map. Or in other words, we have to know its automorphism group. In general, this is an interesting, complicated, and difficult problem. In order to do this, the first problem we meet is how to make a map considered without symmetry. Since the beginning of sixties when Tutte found a way of rooting on a map, the problem has been solved. This forms the basis of the enumerative theory of maps. As soon as the problem without considering the symmetry is solved for one kind of map, the general problem with symmetry can always, in principle, be solved from what we have known about the automorphism of a polyhedron, a synonym for a map, which can be determined efficiently according to another monograph of the present author Liu58]."

"Lectures on Finitely Generated Solvable Groups" are based on the Topics in Group Theory" course focused on finitely generated solvable groups that was given by Gilbert G. Baumslag at the Graduate School and University Center of the City University of New York. While knowledge about finitely generated nilpotent groups is extensive, much less is known about the more general class of solvable groups containing them. The study of finitely generated solvable groups involves many different threads; thereforethese notes contain discussions on HNN extensions; amalgamated and wreath products; and other concepts from combinatorial group theory as well as commutative algebra. Along with Baumslag s Embedding Theorem for Finitely Generated Metabelian Groups, two theorems of Bieri and Strebel are presented to provide a solid foundation for understanding the fascinating class of finitely generated solvable groups. Examples are also supplied, which help illuminate many of the key concepts contained in the notes. Requiring only a modest initial group theory background from graduate and post-graduate students, these notes provide a field guide to the class of finitely generated solvable groups froma combinatorial group theory perspective. "

This book contains a detailed mathematical analysis of the variational approach to image restoration based on the minimization of the total variation submitted to the constraints given by the image acquisition model. This model, initially introduced by Rudin, Osher, and Fatemi, had a strong influence in the development of variational methods for image denoising and restoration, and pioneered the use of the BV model in image processing. After a full analysis of the model, the minimizing total variation flow is studied under different boundary conditions, and its main qualitative properties are exhibited. In particular, several explicit solutions of the denoising problem are computed.

'MathPhys Odyssey 2001' will serve as an excellent reference text for mathematical physicists and graduate students in a number of areas.; Kashiwara/Miwa have a good track record with both SV and Birkhauser.

The articles collected in this volume represent the contributions presented at the IMA workshop on "Dynamics of Algorithms" which took place in November 1997. The workshop was an integral part of the 1997 -98 IMA program on "Emerging Applications of Dynamical Systems." The interaction between algorithms and dynamical systems is mutually beneficial since dynamical methods can be used to study algorithms that are applied repeatedly. Convergence, asymptotic rates are indeed dynamical properties. On the other hand, the study of dynamical systems benefits enormously from having efficient algorithms to compute dynamical objects.

Most people tend to view number theory as the very paradigm of pure mathematics. With the advent of computers, however, number theory has been finding an increasing number of applications in practical settings, such as in cryptography, random number generation, coding theory, and even concert hall acoustics. Yet other applications are still emerging - providing number theorists with some major new areas of opportunity. The 1996 IMA summer program on Emerging Applications of Number Theory was aimed at stimulating further work with some of these newest (and most attractive) applications. Concentration was on number theory's recent links with: (a) wave phenomena in quantum mechanics (more specifically, quantum chaos); and (b) graph theory (especially expander graphs and related spectral theory). This volume contains the contributed papers from that meeting and will be of interest to anyone intrigued by novel applications of modern number-theoretical techniques.

Written by an authority with great practical and teaching experience in the field, this book addresses a number of topics in computational number theory. Chapters one through five form a homogenous subject matter suitable for a six-month or year-long course in computational number theory. The subsequent chapters deal with more miscellaneous subjects.