This book is a collection of articles studying various Steiner tree prob lems with applications in industries, such as the design of electronic cir cuits, computer networking, telecommunication, and perfect phylogeny. The Steiner tree problem was initiated in the Euclidean plane. Given a set of points in the Euclidean plane, the shortest network interconnect ing the points in the set is called the Steiner minimum tree. The Steiner minimum tree may contain some vertices which are not the given points. Those vertices are called Steiner points while the given points are called terminals. The shortest network for three terminals was first studied by Fermat (1601-1665). Fermat proposed the problem of finding a point to minimize the total distance from it to three terminals in the Euclidean plane. The direct generalization is to find a point to minimize the total distance from it to n terminals, which is still called the Fermat problem today. The Steiner minimum tree problem is an indirect generalization. Schreiber in 1986 found that this generalization (i.e., the Steiner mini mum tree) was first proposed by Gauss."

Arc Routing: Theory, Solutions and Applications is about arc traversal and the wide variety of arc routing problems, which has had its foundations in the modern graph theory work of Leonhard Euler. Arc routing methods and computation has become a fundamental optimization concept in operations research and has numerous applications in transportation, telecommunications, manufacturing, the Internet, and many other areas of modern life. The book draws from a variety of sources including the traveling salesman problem (TSP) and graph theory, which are used and studied by operations research, engineers, computer scientists, and mathematicians. In the last ten years or so, there has been extensive coverage of arc routing problems in the research literature, especially from a graph theory perspective; however, the field has not had the benefit of a uniform, systematic treatment. With this book, there is now a single volume that focuses on state-of-the-art exposition of arc routing problems, that explores its graph theoretical foundations, and that presents a number of solution methodologies in a variety of application settings. Moshe Dror has succeeded in working with an elite group of ARC routing scholars to develop the highest quality treatment of the current state-of-the-art in arc routing.

New and striking results obtained in recent years from an intensive study of asymptotic combinatorics have led to a new, higher level of understanding of related problems: the theory of integrable systems, the Riemann-Hilbert problem, asymptotic representation theory, spectra of random matrices, combinatorics of Young diagrams and permutations, and even some aspects of quantum field theory.

This is a new edited volume on shape analysis presenting results in shape modeling and computational geometry from the 2013 Association for Women in Mathematics (AWM) symposium held at UCLA's Institute for Pure and Applied Mathematics (IPAM). In-depth discussion of shape modeling techniques is supplemented by full-color illustrations demonstrating the results of workshop-developed shape modeling algorithms. It will be the first volume in Springer's AWM series.

This book consists of contributions from experts, presenting a fruitful interplay between different approaches to discrete geometry. Most of the chapters were collected at the conference "Geometry and Symmetry" in Veszprem, Hungary from 29 June to 3 July 2015. The conference was dedicated to Karoly Bezdek and Egon Schulte on the occasion of their 60th birthdays, acknowledging their highly regarded contributions in these fields. While the classical problems of discrete geometry have a strong connection to geometric analysis, coding theory, symmetry groups, and number theory, their connection to combinatorics and optimization has become of particular importance. The last decades have seen a revival of interest in discrete geometric structures and their symmetry. The rapid development of abstract polytope theory has resulted in a rich theory featuring an attractive interplay of methods and tools from discrete geometry, group theory and geometry, combinatorial group theory, and hyperbolic geometry and topology. This book contains papers on new developments in these areas, including convex and abstract polytopes and their recent generalizations, tiling and packing, zonotopes, isoperimetric inequalities, and on the geometric and combinatorial aspects of linear optimization. The book is a valuable resource for researchers, both junior and senior, in the field of discrete geometry, combinatorics, or discrete optimization. Graduate students find state-of-the-art surveys and an open problem collection.

This comprehensive textbook on combinatorial optimization places special emphasis on theoretical results and algorithms with provably good performance, in contrast to heuristics. It is based on numerous courses on combinatorial optimization and specialized topics, mostly at graduate level. This book reviews the fundamentals, covers the classical topics (paths, flows, matching, matroids, NP-completeness, approximation algorithms) in detail, and proceeds to advanced and recent topics, some of which have not appeared in a textbook before. Throughout, it contains complete but concise proofs, and also provides numerous exercises and references. This sixth edition has again been updated, revised, and significantly extended. Among other additions, there are new sections on shallow-light trees, submodular function maximization, smoothed analysis of the knapsack problem, the (ln 4+e)-approximation for Steiner trees, and the VPN theorem. Thus, this book continues to represent the state of the art of combinatorial optimization.

A transfinite graph or electrical network of the first rank is obtained conceptually by connecting conventionally infinite graphs and networks together at their infinite extremities. This process can be repeated to obtain a hierarchy of transfiniteness whose ranks increase through the countable ordinals. This idea, which is of recent origin, has enriched the theories of graphs and networks with radically new constructs and research problems. The book provides a more accessible introduction to the subject that, though sacrificing some generality, captures the essential ideas of transfiniteness for graphs and networks. Thus, for example, some results concerning discrete potentials and random walks on transfinite networks can now be presented more concisely. Conversely, the simplifications enable the development of many new results that were previously unavailable. Topics and features: *A simplified exposition provides an introduction to transfiniteness for graphs and networks.*Various results for conventional graphs are extended transfinitely. *Minty's powerful analysis of monotone electrical networks is also extended transfinitely.*Maximum principles for node voltages in linear transfinite networks are established. *A concise treatment of random walks on transfinite networks is developed. *Conventional theory is expanded with radically new constructs. Mathematicians, operations researchers and electrical engineers, in particular, graph theorists, electrical circuit theorists, and probabalists will find an accessible exposition of an advanced subject.

In recent years graph theory has emerged as a subject in its own right, as well as being an important mathematical tool in such diverse subjects as operational research, chemistry, sociology and genetics. Robin Wilson's book has been widely used as a text for undergraduate courses in mathematics, computer science and economics, and as a readable introduction to the subject for non-mathematicians.
The opening chapters provide a basic foundation course, containing definitions and examples, connectedness, Eulerian and Hamiltonian paths and cycles, and trees, with a range of applications. This is followed by two chapters on planar graphs and colouring, with special reference to the four-colour theorem. The next chapter deals with transversal theory and connectivity, with applications to network flows. A final chapter on matroid theory ties together material from earlier chapters, and an appendix discusses algorithms and their efficiency.

The subject of pattern analysis and recognition pervades many aspects of our daily lives, including user authentication in banking, object retrieval from databases in the consumer sector, and the omnipresent surveillance and security measures around sensitive areas. Shape analysis, a fundamental building block in many approaches to these applications, is also used in statistics, biomedical applications (Magnetic Resonance Imaging), and many other related disciplines.

With contributions from some of the leading experts and pioneers in the field, this self-contained, unified volume is the first comprehensive treatment of theory, methods, and algorithms available in a single resource. Developments are discussed from a rapidly increasing number of research papers in diverse fields, including the mathematical and physical sciences, engineering, and medicine.

Preliminary Text. Do not use. Sphere Packings is one of the most attractive and challenging subjects in mathematics. Almost 4 centuries ago, Kepler studied the densities of sphere packings and made his famous conjecture. In the course of centuries, many exciting results have been obtained, ingenious methods created, related challenging problems proposed, and many surprising connections with othe subjects found. Thus, though some of its original problems are still open, sphere packings has been developed into an important discipline. This book tries to give a full account of this fascinating subject, especially its local aspects, discrete aspects and its proof methods.

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.

This book is concerned with the structure of linear semigroups, that is, subsemigroups of the multiplicative semigroup Mn(K) of n x n matrices over a field K (or, more generally, skew linear semigroups - if K is allowed to be a division ring) and its applications to certain problems on associative algebras, semigroups and linear representations. It is motivated by several recent developments in the area of linear semigroups and their applications. It summarizes the state of knowledge in this area, presenting the results for the first time in a unified form. The book's point of departure is a structure theorem, which allows the use of powerful techniques of linear groups. Certain aspects of a combinatorial nature, connections with the theory of linear representations and applications to various problems on associative algebras are also discussed.

This book contains two contributions: "Combinatorial and Asymptotic Methods in Algebra" by V.A. Ufnarovskij is a survey of various combinatorial methods in infinite-dimensional algebras, widely interpreted to contain homological algebra and vigorously developing computer algebra, and narrowly interpreted as the study of algebraic objects defined by generators and their relations. The author shows how objects like words, graphs and automata provide valuable information in asymptotic studies. The main methods emply the notions of Grobner bases, generating functions, growth and those of homological algebra. Treated are also problems of relationships between different series, such as Hilbert, Poincare and Poincare-Betti series. Hyperbolic and quantum groups are also discussed. The reader does not need much of background material for he can find definitions and simple properties of the defined notions introduced along the way. "Non-Associative Structures" by E.N.Kuz'min and I.P.Shestakov surveys the modern state of the theory of non-associative structures that are nearly associative. Jordan, alternative, Malcev, and quasigroup algebras are discussed as well as applications of these structures in various areas of mathematics and primarily their relationship with the associative algebras. Quasigroups and loops are treated too. The survey is self-contained and complete with references to proofs in the literature. The book will be of great interest to graduate students and researchers in mathematics, computer science and theoretical physics."

Orthogonal designs have proved fundamental to constructing code division multiple antenna systems for more efficient mobile communications. Starting with basic theory, this book develops the algebra and combinatorics to create new communications modes. Intended primarily for researchers, it is also useful for graduate students wanting to understand some of the current communications coding theories.

In the course of fuzzy technological development, fuzzy graph theory was identified quite early on for its importance in making things work. Two very important and useful concepts are those of granularity and of nonlinear ap proximations. The concept of granularity has evolved as a cornerstone of Lotfi A.Zadeh's theory of perception, while the concept of nonlinear approx imation is the driving force behind the success of the consumer electronics products manufacturing. It is fair to say fuzzy graph theory paved the way for engineers to build many rule-based expert systems. In the open literature, there are many papers written on the subject of fuzzy graph theory. However, there are relatively books available on the very same topic. Professors' Mordeson and Nair have made a real contribution in putting together a very com prehensive book on fuzzy graphs and fuzzy hypergraphs. In particular, the discussion on hypergraphs certainly is an innovative idea. For an experienced engineer who has spent a great deal of time in the lab oratory, it is usually a good idea to revisit the theory. Professors Mordeson and Nair have created such a volume which enables engineers and design ers to benefit from referencing in one place. In addition, this volume is a testament to the numerous contributions Professor John N. Mordeson and his associates have made to the mathematical studies in so many different topics of fuzzy mathematics."

A combinatorial method is developed in this book to explore the mysteries of chaos, which has became a topic of science since 1975. Using tools from theoretical computer science, formal languages and automata, the complexity of symbolic behaviors of dynamical systems is classified and analysed thoroughly. This book is mainly devoted to explanation of this method and apply it to one-dimensional dynamical systems, including the circle and interval maps, which are typical in exhibiting complex behavior through simple iterated calculations. The knowledge for reading it is self-contained in the book.

In 2006 a special semester on Gr] obner bases and related methods was or- nized by RICAM and RISC, directed by Bruno Buchberger and Heinz Engl. The main focus of the semester were the development of the formal theory of Gr] obner bases (brie?y GB), the e?cient implementation of all algorithms related to this theory, and the promotion of recent and new applications of GB. The workshop D1 "Gr] obner bases in cryptography, coding theory and - gebraic combinatorics," Linz, May 1-6, 2006 (chairmen M. Klin, L. Perret, M. Sala) was one of the main ingredients of the semester. The last two days of this workshop, devoted to combinatorics, made it possible to bring together experts in algorithmic problems related to coherent con?gurations and as- ciation schemes with a community of people working in the area of GB. Each side was interested in understanding the computational problems and current algorithmicpossibilitiesoftheother, withaparticularobjectiveofintroducing the practical use of GB in algebraic combinatorics. Materials (mainly slides of lectures and posters) available from the site http: //www.ricam.oeaw.ac.at/specsem/srs/groeb/schedule D1.htmlprovidea helpful and vivid picture of the successful exchange of scienti?c information during the workshop D1. Asafollow-uptothespecialsemester,10volumesofproceedingsarebeing published by di?erent publishers. The current collection of papers re?ects diverse investigations in the area of algebraic combinatorics (with or without explicit use of GB), but with a de?nite emphasis on algorithmic approaches."

This volume contains selected refereed papers based on lectures presented at the "Integers Conference 2011", an international conference in combinatorial number theory that was held in Carrollton, Georgia, United States in October 2011. This was the fifth Integers Conference, held bi-annually since 2003. It featured plenary lectures presented by Ken Ono, Carla Savage, Laszlo Szekely, Frank Thorne, and Julia Wolf, along with sixty other research talks. This volume consists of ten refereed articles, which are expanded and revised versions of talks presented at the conference. They represent a broad range of topics in the areas of number theory and combinatorics including multiplicative number theory, additive number theory, game theory, Ramsey theory, enumerative combinatorics, elementary number theory, the theory of partitions, and integer sequences.

The book has many important features which make it suitable for both undergraduate and postgraduate students in various branches of engineering and general and applied sciences. The important topics interrelating Mathematics & Computer Science are also covered briefly. The book is useful to readers with a wide range of backgrounds including Mathematics, Computer Science/Computer Applications and Operational Research. While dealing with theorems and algorithms, emphasis is laid on constructions which consist of formal proofs, examples with applications. Uptill, there is scarcity of books in the open literature which cover all the things including most importantly various algorithms and applications with examples.

This book proposes representations of multicast rate regions in wireless networks based on the mathematical concept of submodular functions, e.g., the submodular cut model and the polymatroid broadcast model. These models subsume and generalize the graph and hypergraph models. The submodular structure facilitates a dual decomposition approach to network utility maximization problems, which exploits the greedy algorithm for linear programming on submodular polyhedra. This approach yields computationally efficient characterizations of inner and outer bounds on the multicast capacity regions for various classes of wireless networks.

A unified, modern treatment of the theory of random graphs-including recent results and techniques

Since its inception in the 1960s, the theory of random graphs has evolved into a dynamic branch of discrete mathematics. Yet despite the lively activity and important applications, the last comprehensive volume on the subject is Bollobas's well-known 1985 book. Poised to stimulate research for years to come, this new work covers developments of the last decade, providing a much-needed, modern overview of this fast-growing area of combinatorics. Written by three highly respected members of the discrete mathematics community, the book incorporates many disparate results from across the literature, including results obtained by the authors and some completely new results. Current tools and techniques are also thoroughly emphasized. Clear, easily accessible presentations make Random Graphs an ideal introduction for newcomers to the field and an excellent reference for scientists interested in discrete mathematics and theoretical computer science. Special features include:

• A focus on the fundamental theory as well as basic models of random graphs
• A detailed description of the phase transition phenomenon
• Easy-to-apply exponential inequalities for large deviation bounds
• An extensive study of the problem of containing small subgraphs
• Results by Bollobas and others on the chromatic number of random graphs
• The result by Robinson and Wormald on the existence of Hamilton cycles in random regular graphs
• A gentle introduction to the zero-one laws
• Ample exercises, figures, and bibliographic references

This monograph presents a unified exposition of latin squares and mutually orthogonal sets of latin squares based on groups. Its focus is on orthomorphisms and complete mappings of finite groups, while also offering a complete proof of the Hall-Paige conjecture. The use of latin squares in constructions of nets, affine planes, projective planes, and transversal designs also motivates this inquiry. The text begins by introducing fundamental concepts, like the tests for determining whether a latin square is based on a group, as well as orthomorphisms and complete mappings. From there, it describes the existence problem for complete mappings of groups, building up to the proof of the Hall-Paige conjecture. The third part presents a comprehensive study of orthomorphism graphs of groups, while the last part provides a discussion of Cartesian projective planes, related combinatorial structures, and a list of open problems. Expanding the author's 1992 monograph, Orthomorphism Graphs of Groups, this book is an essential reference tool for mathematics researchers or graduate students tackling latin square problems in combinatorics. Its presentation draws on a basic understanding of finite group theory, finite field theory, linear algebra, and elementary number theory-more advanced theories are introduced in the text as needed.

This volume contains the proceedings of the NATO Advanced Study Institute "Symmetric Functions 2001: Surveys of Developments and Per- spectives", held at the Isaac Newton Institute for Mathematical Sciences in Cambridge, UK, during the two weeks 25 June - 6 July 2001. The objective of the ASI was to survey recent developments and outline research perspectives in various fields, for which the fundamental questions can be stated in the language of symmetric functions (along the way emphasizing interdisciplinary connections). The instructional goals of the event determined its format: the ASI consisted of about a dozen mini-courses. Seven of them served as a basis for the papers comprising the current volume. The ASI lecturers were: Persi Diaconis, William Fulton, Mark Haiman, Phil Hanlon, Alexander Klyachko, Bernard Leclerc, Ian G. Macdonald, Masatoshi Noumi, Andrei Okounkov, Grigori Olshanski, Eric Opdam, Ana- toly Vershik, and Andrei Zelevinsky. The organizing committee consisted of Phil Hanlon, Ian Macdonald, Andrei 0 kounkov, G rigori 0 lshanski (co-director), and myself ( co-director). The original ASI co-director Sergei Kerov, who was instrumental in determining the format and scope of the event, selection of speakers, and drafting the initial grant proposal, died in July 2000. Kerov's mathemat- ical ideas strongly influenced the field, and were presented at length in a number of ASI lectures. A special afternoon session on Monday, July 2, was dedicated to his memory.

The theory of table algebras was introduced in 1991 by Z. Arad and H. Blau in order to treat, in a uniform way, products of conjugacy classes and irreducible characters of finite groups. Today, table algebra theory is a well-established branch of modern algebra with various applications, including the representation theory of finite groups, algebraic combinatorics and fusion rules algebras. This book presents the latest developments in this area. Its main goal is to give a classification of the Normalized Integral Table Algebras (Fusion Rings) generated by a faithful non-real element of degree 3. Divided into 4 parts, the first gives an outline of the classification approach, while remaining parts separately treat special cases that appear during classification. A particularly unique contribution to the field, can be found in part four, whereby a number of the algebras are linked to the polynomial irreducible representations of the group SL3(C). This book will be of interest to research mathematicians and PhD students working in table algebras, group representation theory, algebraic combinatorics and integral fusion rule algebras.

The present volume is a tribute to Gian-Carlo Rota. It is an anthology of the production of a unique collaboration among leading researchers who were greatly influenced by Gian-Carlo Rota's mathematical thought.The book begins with an essay in mathematical biography by H. Crapo in which the prospects for research opened up by Rota's work are outlined. The subsequent section is devoted to the prestigious Fubini lectures delivered by Gian-Carlo Rota at the Institute for scientific Interchange in 1998, with a preface by E. Vesentini. These lectures provide the only published documentation of Rota's plans for a fundamental reform of probability theory, a program interrupted by his untimely demise.The lectures by M. Aigner and D. Perrin specially conceived for this volume, provide self-contained surveys of central topics in combinatorics and theoretical computer science; they will also be of great use to both undergraduate and graduate students.The essays and research papers that appear in the final section present recent developments of some of the mathematical themes promoted by Gian-Carlo Rota. These will be of particular interest as they propose many new problems for research.