Algorithmic Graph Theory and Perfect Graphs, first published in 1980, has become the classic introduction to the field. This new Annals edition continues to convey the message that intersection graph models are a necessary and important tool for solving real-world problems. It remains a stepping stone from which the reader may embark on one of many fascinating research trails.
The past twenty years have been an amazingly fruitful period of research in algorithmic graph theory and structured families of graphs. Especially important have been the theory and applications of new intersection graph models such as generalizations of permutation graphs and interval graphs. These have lead to new families of perfect graphs and many algorithmic results. These are surveyed in the new Epilogue chapter in this second edition.
-New edition of the "Classic" book on the topic
-Wonderful introduction to a rich research area
-Leading author in the field of algorithmic graph theory
-Beautifully written for the new mathematician or computer scientist
-Comprehensive treatment

Interest in finite automata theory continues to grow, not only because of its applications in computer science, but also because of more recent applications in mathematics, particularly group theory and symbolic dynamics. The subject itself lies on the boundaries of mathematics and computer science, and with a balanced approach that does justice to both aspects, this book provides a well-motivated introduction to the mathematical theory of finite automata. The first half of Finite Automata focuses on the computer science side of the theory and culminates in Kleene's Theorem, which the author proves in a variety of ways to suit both computer scientists and mathematicians. In the second half, the focus shifts to the mathematical side of the theory and constructing an algebraic approach to languages. Here the author proves two main results: Schutzenberger's Theorem on star-free languages and the variety theorem of Eilenberg and Schutzenberger. Accessible even to students with only a basic knowledge of discrete mathematics, this treatment develops the underlying algebra gently but rigorously, and nearly 200 exercises reinforce the concepts. Whether your students' interests lie in computer science or mathematics, the well organized and flexible presentation of Finite Automata provides a route to understanding that you can tailor to their particular tastes and abilities.

A remarkable interplay exists between the fields of elliptic functions and orthogonal polynomials. In the first monograph to explore their connections, Elliptic Polynomials combines these two areas of study, leading to an interesting development of some basic aspects of each. It presents new material about various classes of polynomials and about the odd Jacobi elliptic functions and their inverses. The term elliptic polynomials refers to the polynomials generated by odd elliptic integrals and elliptic functions. In studying these, the authors consider such things as orthogonality and the construction of weight functions and measures, finding structure constants and interesting inequalities, and deriving useful formulas and evaluations. Although some of the material may be familiar, it establishes a new mathematical field that intersects with classical subjects at many points. Its wealth of information on important properties of polynomials and clear, accessible presentation make Elliptic Polynomials valuable to those in real and complex analysis, number theory, and combinatorics, and will undoubtedly generate further research.

Near Rings, Fuzzy Ideals, and Graph Theory explores the relationship between near rings and fuzzy sets and between near rings and graph theory. It covers topics from recent literature along with several characterizations. After introducing all of the necessary fundamentals of algebraic systems, the book presents the essentials of near rings theory, relevant examples, notations, and simple theorems. It then describes the prime ideal concept in near rings, takes a rigorous approach to the dimension theory of N-groups, gives some detailed proofs of matrix near rings, and discusses the gamma near ring, which is a generalization of both gamma rings and near rings. The authors also provide an introduction to fuzzy algebraic systems, particularly the fuzzy ideals of near rings and gamma near rings. The final chapter explains important concepts in graph theory, including directed hypercubes, dimension, prime graphs, and graphs with respect to ideals in near rings. Near ring theory has many applications in areas as diverse as digital computing, sequential mechanics, automata theory, graph theory, and combinatorics. Suitable for researchers and graduate students, this book provides readers with an understanding of near ring theory and its connection to fuzzy ideals and graph theory.

This volume consists of research papers and expository survey articles presented by the invited speakers of the Summer Workshop on Lattice Polytopes. Topics include enumerative, algebraic and geometric combinatorics on lattice polytopes, topological combinatorics, commutative algebra and toric varieties.Readers will find that this volume showcases current trends on lattice polytopes and stimulates further developments of many research areas surrounding this field. With the survey articles, research papers and open problems, this volume provides its fundamental materials for graduate students to learn and researchers to find exciting activities and avenues for further exploration on lattice polytopes.

An update of the most accessible introductory number theory text available, Fundamental Number Theory with Applications, Second Edition presents a mathematically rigorous yet easy-to-follow treatment of the fundamentals and applications of the subject. The substantial amount of reorganizing makes this edition clearer and more elementary in its coverage. New to the Second Edition * Removal of all advanced material to be even more accessible in scope * New fundamental material, including partition theory, generating functions, and combinatorial number theory * Expanded coverage of random number generation, Diophantine analysis, and additive number theory * More applications to cryptography, primality testing, and factoring * An appendix on the recently discovered unconditional deterministic polynomial-time algorithm for primality testing Taking a truly elementary approach to number theory, this text supplies the essential material for a first course on the subject. Placed in highlighted boxes to reduce distraction from the main text, nearly 70 biographies focus on major contributors to the field. The presentation of over 1,300 entries in the index maximizes cross-referencing so students can find data with ease.

Researchers and practitioners of cryptography and information security are constantly challenged to respond to new attacks and threats to information systems. Authentication Codes and Combinatorial Designs presents new findings and original work on perfect authentication codes characterized in terms of combinatorial designs, namely strong partially balanced designs (SPBD). Beginning with examples illustrating the concepts of authentication schemes and combinatorial designs, the book considers the probability of successful deceptions followed by schemes involving three and four participants, respectively. From this point, the author constructs the perfect authentication schemes and explores encoding rules for such schemes in some special cases. Using rational normal curves in projective spaces over finite fields, the author constructs a new family of SPBD. He then presents some established combinatorial designs that can be used to construct perfect schemes, such as t-designs, orthogonal arrays of index unity, and designs constructed by finite geometry. The book concludes by studying definitions of perfect secrecy, properties of perfectly secure schemes, and constructions of perfect secrecy schemes with and without authentication. Supplying an appendix of construction schemes for authentication and secrecy schemes, Authentication Codes and Combinatorial Designs points to new applications of combinatorial designs in cryptography.

Sums of Squares of Integers covers topics in combinatorial number theory as they relate to counting representations of integers as sums of a certain number of squares. The book introduces a stimulating area of number theory where research continues to proliferate. It is a book of "firsts" - namely it is the first book to combine Liouville's elementary methods with the analytic methods of modular functions to study the representation of integers as sums of squares. It is the first book to tell how to compute the number of representations of an integer n as the sum of s squares of integers for any s and n. It is also the first book to give a proof of Szemeredi's theorem, and is the first number theory book to discuss how the modern theory of modular forms complements and clarifies the classical fundamental results about sums of squares. The book presents several existing, yet still interesting and instructive, examples of modular forms. Two chapters develop useful properties of the Bernoulli numbers and illustrate arithmetic progressions, proving the theorems of van der Waerden, Roth, and Szemeredi. The book also explains applications of the theory to three problems that lie outside of number theory in the areas of cryptanalysis, microwave radiation, and diamond cutting. The text is complemented by the inclusion of over one hundred exercises to test the reader's understanding.

The third edition of this definitive and popular book continues to pursue the question: what is the most efficient way to pack a large number of equal spheres in n-dimensional Euclidean space? The authors also examine such related issues as the kissing number problem, the covering problem, the quantizing problem, and the classification of lattices and quadratic forms. There is also a description of the applications of these questions to other areas of mathematics and science such as number theory, coding theory, group theory, analogue-to-digital conversion and data compression, n-dimensional crystallography, dual theory and superstring theory in physics. New and of special interest is a report on some recent developments in the field, and an updated and enlarged supplementary bibliography with over 800 items.

An effective blend of carefully explained theory and practical applications, this text imparts the fundamentals of both information theory and data compression. Although the two topics are related, this unique text allows either topic to be presented independently, and it was specifically designed so that the data compression section requires no prior knowledge of information theory. The treatment of information theory, while theoretical and abstract, is quite elementary, making this text less daunting than many others. After presenting the fundamental definitions and results of the theory, the authors then apply the theory to memoryless, discrete channels with zeroth-order, one-state sources. The chapters on data compression acquaint students with a myriad of lossless compression methods and then introduce two lossy compression methods. Students emerge from this study competent in a wide range of techniques. The authors' presentation is highly practical but includes some important proofs, either in the text or in the exercises, so instructors can, if they choose, place more emphasis on the mathematics. Introduction to Information Theory and Data Compression, Second Edition is ideally suited for an upper-level or graduate course for students in mathematics, engineering, and computer science. Features: Expanded discussion of the historical and theoretical basis of information theory that builds a firm, intuitive grasp of the subject Reorganization of theoretical results along with new exercises, ranging from the routine to the more difficult, that reinforce students' ability to apply the definitions and results in specific situations. Simplified treatment of the algorithm(s) of Gallager and Knuth Discussion of the information rate of a code and the trade-off between error correction and information rate Treatment of probabilistic finite state source automata, including basic resul

The advancement of large scale integrated circuit technology has enabled the construction of complex interconnection networks. Graph theory provides a fundamental tool for designing and analyzing such networks. Graph Theory and Interconnection Networks provides a thorough understanding of these interrelated topics. After a brief introduction to graph terminology, the book presents well-known interconnection networks as examples of graphs, followed by in-depth coverage of Hamiltonian graphs. Different types of problems illustrate the wide range of available methods for solving such problems. The text also explores recent progress on the diagnosability of graphs under various models.

This book presents open optimization problems in graph theory and networks. Each chapter reflects developments in theory and applications based on Gregory Gutin's fundamental contributions to advanced methods and techniques in combinatorial optimization. Researchers, students, and engineers in computer science, big data, applied mathematics, operations research, algorithm design, artificial intelligence, software engineering, data analysis, industrial and systems engineering will benefit from the state-of-the-art results presented in modern graph theory and its applications to the design of efficient algorithms for optimization problems. Topics covered in this work include: * Algorithmic aspects of problems with disjoint cycles in graphs * Graphs where maximal cliques and stable sets intersect * The maximum independent set problem with special classes * A general technique for heuristic algorithms for optimization problems * The network design problem with cut constraints * Algorithms for computing the frustration index of a signed graph * A heuristic approach for studying the patrol problem on a graph * Minimum possible sum and product of the proper connection number * Structural and algorithmic results on branchings in digraphs * Improved upper bounds for Korkel--Ghosh benchmark SPLP instances

Based on talks from the 2015 and 2016 Combinatorial and Additive Number Theory (CANT) workshops at the City University of New York, these proceedings offer 19 peer-reviewed and edited papers on current topics in number theory. Held every year since 2003, the workshop series surveys state-of-the-art open problems in combinatorial and additive number theory and related parts of mathematics. Sumsets, partitions, convex polytopes and discrete geometry, Ramsey theory, primality testing, and cryptography are among the topics featured in this volume. Each contribution is dedicated to a specific topic that reflects the latest results by experts in the field. Researchers and graduate students interested in the current progress in number theory will find this selection of articles relevant and compelling.

Geometric Data Analysis designates the approach of Multivariate Statistics that conceptualizes the set of observations as a Euclidean cloud of points. Combinatorial Inference in Geometric Data Analysis gives an overview of multidimensional statistical inference methods applicable to clouds of points that make no assumption on the process of generating data or distributions, and that are not based on random modelling but on permutation procedures recasting in a combinatorial framework. It focuses particularly on the comparison of a group of observations to a reference population (combinatorial test) or to a reference value of a location parameter (geometric test), and on problems of homogeneity, that is the comparison of several groups for two basic designs. These methods involve the use of combinatorial procedures to build a reference set in which we place the data. The chosen test statistics lead to original extensions, such as the geometric interpretation of the observed level, and the construction of a compatibility region. Features: Defines precisely the object under study in the context of multidimensional procedures, that is clouds of points Presents combinatorial tests and related computations with R and Coheris SPAD software Includes four original case studies to illustrate application of the tests Includes necessary mathematical background to ensure it is self-contained This book is suitable for researchers and students of multivariate statistics, as well as applied researchers of various scientific disciplines. It could be used for a specialized course taught at either master or PhD level.

Computational Complexity of Counting and Sampling provides readers with comprehensive and detailed coverage of the subject of computational complexity. It is primarily geared toward researchers in enumerative combinatorics, discrete mathematics, and theoretical computer science. The book covers the following topics: Counting and sampling problems that are solvable in polynomial running time, including holographic algorithms; #P-complete counting problems; and approximation algorithms for counting and sampling. First, it opens with the basics, such as the theoretical computer science background and dynamic programming algorithms. Later, the book expands its scope to focus on advanced topics, like stochastic approximations of counting discrete mathematical objects and holographic algorithms. After finishing the book, readers will agree that the subject is well covered, as the book starts with the basics and gradually explores the more complex aspects of the topic. Features: Each chapter includes exercises and solutions Ideally written for researchers and scientists Covers all aspects of the topic, beginning with a solid introduction, before shifting to computational complexity's more advanced features, with a focus on counting and sampling

This book presents works detailing the application of processing and visualization techniques for analyzing the Earth's subsurface. The topic of the book is interactive data processing and interactive 3D visualization techniques used on subsurface data. Interactive processing of data together with interactive visualization is a powerful combination which has in the recent years become possible due to hardware and algorithm advances in. The combination enables the user to perform interactive exploration and filtering of datasets while simultaneously visualizing the results so that insights can be made immediately. This makes it possible to quickly form hypotheses and draw conclusions. Case studies from the geosciences are not as often presented in the scientific visualization and computer graphics community as e.g., studies on medical, biological or chemical data. This book will give researchers in the field of visualization and computer graphics valuable insight into the open visualization challenges in the geosciences, and how certain problems are currently solved using domain specific processing and visualization techniques. Conversely, readers from the geosciences will gain valuable insight into relevant visualization and interactive processing techniques. Subsurface data has interesting characteristics such as its solid nature, large range of scales and high degree of uncertainty, which makes it challenging to visualize with standard methods. It is also noteworthy that parallel fields of research have taken place in geosciences and in computer graphics, with different terminology when it comes to representing geometry, describing terrains, interpolating data and (example-based) synthesis of data. The domains covered in this book are geology, digital terrains, seismic data, reservoir visualization and CO2 storage. The technologies covered are 3D visualization, visualization of large datasets, 3D modelling, machine learning, virtual reality, seismic interpretation and multidisciplinary collaboration. People within any of these domains and technologies are potential readers of the book.

From Combinatorics to Philosophy: The Legacy of G. -C. Rota provides an assessment of G. -C. Rota's legacy to current international research issues in mathematics, philosophy and computer science.

This volume includes chapters by leading researchers, as well as a number of invited research papers. Rota's legacy connects European and Italian research communities to the USA by providing inspiration to several generations of researchers in combinatorics, philosophy and computer science.

From Combinatorics to Philosophy: The Legacy of G. -C. Rota is of valuable interest to research institutions and university libraries worldwide. This book is also designed for advanced-level students in mathematics, computer science, and philosophy.

The subject of this book is truly original. By encoding of algebraic equations into graphs-originally a purely pedagogical technique-the exploration of physics and physical chemistry reveals common pictures through all disciplines. The hidden structure of the scientific formalism that appears is a source of astonishment and provides efficient simplifications of the representation of physical laws. Understanding Physics and Physical Chemistry Using Formal Graphs is organized according to the structures emerging from formal graphs, from simple to elaborate, providing after each series of case studies the theoretical elements necessary for understanding their common features. More than 80 case studies are tackled in domains ranging from translational mechanics to Newtonian gravitation to chemical reactions. With the help of this new tool, the modeling of physical phenomena becomes a fascinating cross-disciplinary exploration. The graphs encourage a visual, unified comprehension of the relationships between physical concepts and variables, properties, and operators. Out-of-the-box and thought provoking, this book inspires lively discussions and fruitful thinking about the connections between mechanics, chemical reactivity, electrodynamics, thermodynamics, and more.

This textbook explores probability and stochastic processes at a level that does not require any prior knowledge except basic calculus. It presents the fundamental concepts in a step-by-step manner, and offers remarks and warnings for deeper insights. The chapters include basic examples, which are revisited as the new concepts are introduced. To aid learning, figures and diagrams are used to help readers grasp the concepts, and the solutions to the exercises and problems. Further, a table format is also used where relevant for better comparison of the ideas and formulae. The first part of the book introduces readers to the essentials of probability, including combinatorial analysis, conditional probability, and discrete and continuous random variable. The second part then covers fundamental stochastic processes, including point, counting, renewal and regenerative processes, the Poisson process, Markov chains, queuing models and reliability theory. Primarily intended for undergraduate engineering students, it is also useful for graduate-level students wanting to refresh their knowledge of the basics of probability and stochastic processes.

This book is an account of the combinatorics of projective spaces over a finite field, with special emphasis on one and two dimensions. With its successor volumes, Finite projective spaces over three dimensions (1985), which is devoted to three dimensions, and General Galois geometries (1991), on a general dimension, it provides a comprehensive treatise of this area of mathematics. The area is interesting in itself, but is important for its applications to coding theory and statistics, and its use of group theory, algebraic geometry, and number theory. This edition is a complete reworking of the first edition. The chapters bear almost the same titles as the first edition, but every chapter has been changed. The most significant changes are to Chapters 2, 10, 12, 13, which respectively describe generalities, the geometry of arcs in ovals, the geometry of arcs of higher degree, and blocking sets. The book is divided into three parts. The first part comprises two chapters, the first of which is a survey of finite fields; the second outlines the fundamental properties of projective spaces and their automorphisms, as well as properties of algebraic varieties and curves, in particular, that are used in the rest of the book and the accompanying two volumes. Parts II and III are entirely self-contained; all proofs of results are given. The second part comprises Chapters 3 to 5. They cover, in an arbitrary dimension, the properties of subspaces such as their number and characterization, of partitions into both subspaces and subgeometries, and of quadrics and Hermitian varieties, as well as polarities. Part III is a detailed account of the line and the plane. In the plane, fundamental properties are first revisited without much resort to the generalities of Parts I and II. Then, the structure of arcs and their relation to curves is described; this includes arcs both of degree two and higher degrees. There are further chapters on blocking sets and on small planes, which means of orders up to thirteen. A comprehensive bibliography of more than 3000 items is provided. At the end of each chapter is a section, Notes and References, which attributes proofs, includes further comments, and lists every relevant reference from the bibliography.

This research monograph utilizes exact and Monte Carlo permutation statistical methods to generate probability values and measures of effect size for a variety of measures of association. Association is broadly defined to include measures of correlation for two interval-level variables, measures of association for two nominal-level variables or two ordinal-level variables, and measures of agreement for two nominal-level or two ordinal-level variables. Additionally, measures of association for mixtures of the three levels of measurement are considered: nominal-ordinal, nominal-interval, and ordinal-interval measures. Numerous comparisons of permutation and classical statistical methods are presented. Unlike classical statistical methods, permutation statistical methods do not rely on theoretical distributions, avoid the usual assumptions of normality and homogeneity of variance, and depend only on the data at hand. This book takes a unique approach to explaining statistics by integrating a large variety of statistical methods, and establishing the rigor of a topic that to many may seem to be a nascent field. This topic is relatively new in that it took modern computing power to make permutation methods available to those working in mainstream research. Written for a statistically informed audience, it is particularly useful for teachers of statistics, practicing statisticians, applied statisticians, and quantitative graduate students in fields such as psychology, medical research, epidemiology, public health, and biology. It can also serve as a textbook in graduate courses in subjects like statistics, psychology, and biology.

Additive Combinatorics: A Menu of Research Problems is the first book of its kind to provide readers with an opportunity to actively explore the relatively new field of additive combinatorics. The author has written the book specifically for students of any background and proficiency level, from beginners to advanced researchers. It features an extensive menu of research projects that are challenging and engaging at many different levels. The questions are new and unsolved, incrementally attainable, and designed to be approachable with various methods. The book is divided into five parts which are compared to a meal. The first part is called Ingredients and includes relevant background information about number theory, combinatorics, and group theory. The second part, Appetizers, introduces readers to the book's main subject through samples. The third part, Sides, covers auxiliary functions that appear throughout different chapters. The book's main course, so to speak, is Entrees: it thoroughly investigates a large variety of questions in additive combinatorics by discussing what is already known about them and what remains unsolved. These include maximum and minimum sumset size, spanning sets, critical numbers, and so on. The final part is Pudding and features numerous proofs and results, many of which have never been published. Features: The first book of its kind to explore the subject Students of any level can use the book as the basis for research projects The text moves gradually through five distinct parts, which is suitable both for beginners without prerequisites and for more advanced students Includes extensive proofs of propositions and theorems Each of the introductory chapters contains numerous exercises to help readers

This volume offers a valuable starting point for anyone interested in learning computational diffusion MRI and mathematical methods for brain connectivity, while also sharing new perspectives and insights on the latest research challenges for those currently working in the field. Over the last decade, interest in diffusion MRI has virtually exploded. The technique provides unique insights into the microstructure of living tissue and enables in-vivo connectivity mapping of the brain. Computational techniques are key to the continued success and development of diffusion MRI and to its widespread transfer into the clinic, while new processing methods are essential to addressing issues at each stage of the diffusion MRI pipeline: acquisition, reconstruction, modeling and model fitting, image processing, fiber tracking, connectivity mapping, visualization, group studies and inference. These papers from the 2016 MICCAI Workshop "Computational Diffusion MRI" - which was intended to provide a snapshot of the latest developments within the highly active and growing field of diffusion MR - cover a wide range of topics, from fundamental theoretical work on mathematical modeling, to the development and evaluation of robust algorithms and applications in neuroscientific studies and clinical practice. The contributions include rigorous mathematical derivations, a wealth of rich, full-color visualizations, and biologically or clinically relevant results. As such, they will be of interest to researchers and practitioners in the fields of computer science, MR physics, and applied mathematics.

This book concerns comics and what was, in 2003, a developing tradition of Disney-style comic-strips. It also deals with the Dutch graphic artist Maurits Cornelis Escher. Several of his images can be seen in animated form. It also talks of theatre and cinema too. For example, Luca Vigan 's curious theatrical spectacle in Genoa about Evariste Galois. It talks about war and peace, ageless themes. All this and a tribute to the mathematician Ennio De Giorgi.

The connected dominating set has been a classic subject studied in graph theory since 1975. Since the 1990s, it has been found to have important applications in communication networks, especially in wireless networks, as a virtual backbone. Motivated from those applications, many papers have been published in the literature during last 15 years. Now, the connected dominating set has become a hot research topic in computer science. In this book, we are going to collect recent developments on the connected dominating set, which presents the state of the art in the study of connected dominating sets. The book consists of 16 chapters. Except the 1st one, each chapter is devoted to one problem, and consists of three parts, motivation and overview, problem complexity analysis, and approximation algorithm designs, which will lead the reader to see clearly about the background, formulation, existing important research results, and open problems. Therefore, this would be a very valuable reference book for researchers in computer science and operations research, especially in areas of theoretical computer science, computer communication networks, combinatorial optimization, and discrete mathematics.