An approach to complexity theory which offers a means of analysing algorithms in terms of their tractability. The authors consider the problem in terms of parameterized languages and taking "k-slices" of the language, thus introducing readers to new classes of algorithms which may be analysed more precisely than was the case until now. The book is as self-contained as possible and includes a great deal of background material. As a result, computer scientists, mathematicians, and graduate students interested in the design and analysis of algorithms will find much of interest.

The problem of "Shortest Connectivity," which is discussed here, has a long and convoluted history. Many scientists from many fields as well as laymen have stepped on its stage. Usually, the problem is known as Steiner's Problem and it can be described more precisely in the following way: Given a finite set of points in a metric space, search for a network that connects these points with the shortest possible length. This shortest network must be a tree and is called a Steiner Minimal Tree (SMT). It may contain vertices different from the points which are to be connected. Such points are called Steiner points. Steiner's Problem seems disarmingly simple, but it is rich with possibilities and difficulties, even in the simplest case, the Euclidean plane. This is one of the reasons that an enormous volume of literature has been published, starting in 1 the seventeenth century and continuing until today. The difficulty is that we look for the shortest network overall. Minimum span ning networks have been well-studied and solved eompletely in the case where only the given points must be connected. The novelty of Steiner's Problem is that new points, the Steiner points, may be introduced so that an intercon necting network of all these points will be shorter. This also shows that it is impossible to solve the problem with combinatorial and geometric methods alone."

Trees are a fundamental object in graph theory and combinatorics as well as a basic object for data structures and algorithms in computer science. During thelastyearsresearchrelatedto(random)treeshasbeenconstantlyincreasing and several asymptotic and probabilistic techniques have been developed in order to describe characteristics of interest of large trees in di?erent settings. Thepurposeofthisbookistoprovideathoroughintroductionintovarious aspects of trees in randomsettings anda systematic treatment ofthe involved mathematicaltechniques. It shouldserveasa referencebookaswellasa basis for future research. One major conceptual aspect is to connect combinatorial and probabilistic methods that range from counting techniques (generating functions, bijections) over asymptotic methods (singularity analysis, saddle point techniques) to various sophisticated techniques in asymptotic probab- ity (convergence of stochastic processes, martingales). However, the reading of the book requires just basic knowledge in combinatorics, complex analysis, functional analysis and probability theory of master degree level. It is also part of concept of the book to provide full proofs of the major results even if they are technically involved and lengthy.

The quadratic assignment problem (QAP) was introduced in 1957 by Koopmans and Beckmann to model a plant location problem. Since then the QAP has been object of numerous investigations by mathematicians, computers scientists, ope- tions researchers and practitioners. Nowadays the QAP is widely considered as a classical combinatorial optimization problem which is (still) attractive from many points of view. In our opinion there are at last three main reasons which make the QAP a popular problem in combinatorial optimization. First, the number of re- life problems which are mathematically modeled by QAPs has been continuously increasing and the variety of the fields they belong to is astonishing. To recall just a restricted number among the applications of the QAP let us mention placement problems, scheduling, manufacturing, VLSI design, statistical data analysis, and parallel and distributed computing. Secondly, a number of other well known c- binatorial optimization problems can be formulated as QAPs. Typical examples are the traveling salesman problem and a large number of optimization problems in graphs such as the maximum clique problem, the graph partitioning problem and the minimum feedback arc set problem. Finally, from a computational point of view the QAP is a very difficult problem. The QAP is not only NP-hard and - hard to approximate, but it is also practically intractable: it is generally considered as impossible to solve (to optimality) QAP instances of size larger than 20 within reasonable time limits.

'Subdivision' is a way of representing smooth shapes in a computer. A curve or surface (both of which contain an in?nite number of points) is described in terms of two objects. One object is a sequence of vertices, which we visualise as a polygon, for curves, or a network of vertices, which we visualise by drawing the edges or faces of the network, for surfaces. The other object is a set of rules for making denser sequences or networks. When applied repeatedly, the denser and denser sequences are claimed to converge to a limit, which is the curve or surface that we want to represent. This book focusses on curves, because the theory for that is complete enough that a book claiming that our understanding is complete is exactly what is needed to stimulate research proving that claim wrong. Also because there are already a number of good books on subdivision surfaces. The way in which the limit curve relates to the polygon, and a lot of interesting properties of the limit curve, depend on the set of rules, and this book is about how one can deduce those properties from the set of rules, and how one can then use that understanding to construct rules which give the properties that one wants.

This book contains a collection of fifteen articles and is dedicated to the sixtieth birthdays of Lex Renner and Mohan Putcha, the pioneers of the field of algebraic monoids. Topics presented include: structure and representation theory of reductive algebraic monoids monoid schemes and applications of monoids monoids related to Lie theory equivariant embeddings of algebraic groups constructions and properties of monoids from algebraic combinatorics endomorphism monoids induced from vector bundles Hodge-Newton decompositions of reductive monoids A portion of these articles are designed to serve as a self-contained introduction to these topics, while the remaining contributions are research articles containing previously unpublished results, which are sure to become very influential for future work. Among these, for example, the important recent work of Michel Brion and Lex Renner showing that the algebraic semigroups are strongly pi-regular.Graduate students as well as researchers working in the fields of algebraic (semi)group theory, algebraic combinatorics, and the theory of algebraic group embeddings will benefit from this unique and broad compilation of some fundamental results in (semi)group theory, algebraic group embeddings, and algebraic combinatorics merged under the umbrella of algebraic monoids.

This valuable source for graduate students and researchers provides a comprehensive introduction to current theories and applications in optimization methods and network models. Contributions to this book are focused on new efficient algorithms and rigorous mathematical theories, which can be used to optimize and analyze mathematical graph structures with massive size and high density induced by natural or artificial complex networks. Applications to social networks, power transmission grids, telecommunication networks, stock market networks, and human brain networks are presented. Chapters in this book cover the following topics: Linear max min fairness Heuristic approaches for high-quality solutions Efficient approaches for complex multi-criteria optimization problems Comparison of heuristic algorithms New heuristic iterative local search Power in network structures Clustering nodes in random graphs Power transmission grid structure Network decomposition problems Homogeneity hypothesis testing Network analysis of international migration Social networks with node attributes Testing hypothesis on degree distribution in the market graphs Machine learning applications to human brain network studies This proceeding is a result of The 6th International Conference on Network Analysis held at the Higher School of Economics, Nizhny Novgorod in May 2016. The conference brought together scientists and engineers from industry, government, and academia to discuss the links between network analysis and a variety of fields.

A basic problem for the interconnection of communications media is to design interconnection networks for specific needs. For example, to minimize delay and to maximize reliability, networks are required that have minimum diameter and maximum connectivity under certain conditions. The book provides a recent solution to this problem. The subject of all five chapters is the interconnection problem. The first two chapters deal with Cayley digraphs which are candidates for networks of maximum connectivity with given degree and number of nodes. Chapter 3 addresses Bruijn digraphs, Kautz digraphs, and their generalizations, which are candidates for networks of minimum diameter and maximum connectivity with given degree and number of nodes. Chapter 4 studies double loop networks, and Chapter 5 considers broadcasting and the Gossiping problem. All the chapters emphasize the combinatorial aspects of network theory. Audience: A vital reference for graduate students and researchers in applied mathematics and theoretical computer science.

This book presents a large variety of extensions of the methods of inclusion and exclusion. Both methods for generating and methods for proof of such inequalities are discussed. The inequalities are utilized for finding asymptotic values and for limit theorems. Applications vary from classical probability estimates to modern extreme value theory and combinatorial counting to random subset selection. Applications are given in prime number theory, growth of digits in different algorithms, and in statistics such as estimates of confidence levels of simultaneous interval estimation. The prerequisites include the basic concepts of probability theory and familiarity with combinatorial arguments.

In April of 1996 an array of mathematicians converged on Cambridge, Massachusetts, for the Rotafest and Umbral Calculus Workshop, two con ferences celebrating Gian-Carlo Rota's 64th birthday. It seemed appropriate when feting one of the world's great combinatorialists to have the anniversary be a power of 2 rather than the more mundane 65. The over seventy-five par ticipants included Rota's doctoral students, coauthors, and other colleagues from more than a dozen countries. As a further testament to the breadth and depth of his influence, the lectures ranged over a wide variety of topics from invariant theory to algebraic topology. This volume is a collection of articles written in Rota's honor. Some of them were presented at the Rotafest and Umbral Workshop while others were written especially for this Festschrift. We will say a little about each paper and point out how they are connected with the mathematical contributions of Rota himself."

Foremost experts in their field have contributed articles resulting in a compilation of useful and timely surveys in this ever-expanding field. Each of these 12 original papers covers important aspects of design theory including several in areas that have not previously been surveyed. Also contains surveys updating earlier ones where research is particularly active.

Partition functions arise in combinatorics and related problems of statistical physics as they encode in a succinct way the combinatorial structure of complicated systems. The main focus of the book is on efficient ways to compute (approximate) various partition functions, such as permanents, hafnians and their higher-dimensional versions, graph and hypergraph matching polynomials, the independence polynomial of a graph and partition functions enumerating 0-1 and integer points in polyhedra, which allows one to make algorithmic advances in otherwise intractable problems. The book unifies various, often quite recent, results scattered in the literature, concentrating on the three main approaches: scaling, interpolation and correlation decay. The prerequisites include moderate amounts of real and complex analysis and linear algebra, making the book accessible to advanced math and physics undergraduates.

A brilliant treatment of a knotty problem in computing. This volume contains chapters written by reputable researchers and provides the state of the art in theory and algorithms for the traveling salesman problem (TSP). The book covers all important areas of study on TSP, including polyhedral theory for symmetric and asymmetric TSP, branch and bound, and branch and cut algorithms, probabilistic aspects of TSP, and includes a thorough computational analysis of heuristic and metaheuristic algorithms.

Local search has been applied successfully to a diverse collection of optimization problems. However, results are scattered throughout the literature. This is the first book that presents a large collection of theoretical results in a consistent manner. It provides the reader with a coherent overview of the achievements obtained so far, and serves as a source of inspiration for the development of novel results in the challenging field of local search.

A key element of any modern video codec is the efficient exploitation of temporal redundancy via motion-compensated prediction. In this book, a novel paradigm of representing and employing motion information in a video compression system is described that has several advantages over existing approaches. Traditionally, motion is estimated, modelled, and coded as a vector field at the target frame it predicts. While this "prediction-centric" approach is convenient, the fact that the motion is "attached" to a specific target frame implies that it cannot easily be re-purposed to predict or synthesize other frames, which severely hampers temporal scalability. In light of this, the present book explores the possibility of anchoring motion at reference frames instead. Key to the success of the proposed "reference-based" anchoring schemes is high quality motion inference, which is enabled by the use of a more "physical" motion representation than the traditionally employed "block" motion fields. The resulting compression system can support computationally efficient, high-quality temporal motion inference, which requires half as many coded motion fields as conventional codecs. Furthermore, "features" beyond compressibility - including high scalability, accessibility, and "intrinsic" framerate upsampling - can be seamlessly supported. These features are becoming ever more relevant as the way video is consumed continues shifting from the traditional broadcast scenario to interactive browsing of video content over heterogeneous networks. This book is of interest to researchers and professionals working in multimedia signal processing, in particular those who are interested in next-generation video compression. Two comprehensive background chapters on scalable video compression and temporal frame interpolation make the book accessible for students and newcomers to the field.

Numbers, Information and Complexity is a collection of about 50 articles in honour of Rudolf Ahlswede. His main areas of research are represented in the three sections, `Numbers and Combinations', `Information Theory (Channels and Networks, Combinatorial and Algebraic Coding, Cryptology, with the related fields Data Compression, Entropy Theory, Symbolic Dynamics, Probability and Statistics)', and `Complexity'. Special attention was paid to the interplay between the fields. Surveys on topics of current interest are included as well as new research results. The book features surveys on Combinatorics about topics such as intersection theorems, which are not yet covered in textbooks, several contributions by leading experts in data compression, and relations to Natural Sciences are discussed.

Paul Turan, one of the greatest Hungarian mathematicians, was born 100 years ago, on August 18, 1910. To celebrate this occasion the Hungarian Academy of Sciences, the Alfred Renyi Institute of Mathematics, the Janos Bolyai Mathematical Society and the Mathematical Institute of Eoetvoes Lorand University organized an international conference devoted to Paul Turan's main areas of interest: number theory, selected branches of analysis, and selected branches of combinatorics. The conference was held in Budapest, August 22-26, 2011. Some of the invited lectures reviewed different aspects of Paul Turan's work and influence. Most of the lectures allowed participants to report about their own work in the above mentioned areas of mathematics.

This is the first book on the subject since its introduction more than fifty years ago, and it can be used as a graduate text or as a reference work. It features all of the key results, many very useful tables, and a large number of research problems. The book will be of interest to those interested in one of the most fascinating areas of discrete mathematics, connected to statistics and coding theory, with applications to computer science and cryptography. It will be useful for anyone who is running experiments, whether in a chemistry lab or a manufacturing plant (trying to make those alloys stronger), or in agricultural or medical research. Sam Hedayat is Professor of Statistics and Senior Scholar in the Department of Mathematics, Statistics, and Computer Science, University of Illinois, Chicago. Neil J.A. Sloane is with AT&T Bell Labs (now AT&T Labs). John Stufken is Professor Statistics at Iowa State University.

This is the first book on higher dimensional Hadamard matrices and their applications in telecommunications and information security. It is divided into three parts according to the dimensions of the Hadamard matrices treated.

The primary objective of this essential text is to emphasize the deep relations existing between the semiring and dio d structures with graphs and their combinatorial properties. It does so at the same time as demonstrating the modeling and problem-solving flexibility of these structures. In addition the book provides an extensive overview of the mathematical properties employed by "nonclassical" algebraic structures which either extend usual algebra or form a new branch of it.

On March 28~31, 1994 (Farvardin 8~11, 1373 by Iranian calendar), the Twenty fifth Annual Iranian Mathematics Conference (AIMC25) was held at Sharif University of Technology in Tehran, Islamic Republic of Iran. Its sponsors in~ eluded the Iranian Mathematical Society, and the Department of Mathematical Sciences at Sharif University of Technology. Among the keynote speakers were Professor Dr. Andreas Dress and Professor Richard K. Guy. Their plenary lec~ tures on combinatorial themes were complemented by invited and contributed lectures in a Combinatorics Session. This book is a collection of refereed papers, submitted primarily by the participants after the conference. The topics covered are diverse, spanning a wide range of combinatorics and al~ lied areas in discrete mathematics. Perhaps the strength and variety of the pa~ pers here serve as the best indications that combinatorics is advancing quickly, and that the Iranian mathematics community contains very active contributors. We hope that you find the papers mathematically stimulating, and look forward to a long and productive growth of combinatorial mathematics in Iran.

A gentle introduction to the highly sophisticated world of discrete mathematics, Mathematical Problems and Proofs presents topics ranging from elementary definitions and theorems to advanced topics -- such as cardinal numbers, generating functions, properties of Fibonacci numbers, and Euclidean algorithm. This excellent primer illustrates more than 150 solutions and proofs, thoroughly explained in clear language. The generous historical references and anecdotes interspersed throughout the text create interesting intermissions that will fuel readers' eagerness to inquire further about the topics and some of our greatest mathematicians. The author guides readers through the process of solving enigmatic proofs and problems, and assists them in making the transition from problem solving to theorem proving. At once a requisite text and an enjoyable read, Mathematical Problems and Proofs is an excellent entrA(c)e to discrete mathematics for advanced students interested in mathematics, engineering, and science.

One of the major concerns of theoretical computer science is the classifi cation of problems in terms of how hard they are. The natural measure of difficulty of a function is the amount of time needed to compute it (as a function of the length of the input). Other resources, such as space, have also been considered. In recursion theory, by contrast, a function is considered to be easy to compute if there exists some algorithm that computes it. We wish to classify functions that are hard, i.e., not computable, in a quantitative way. We cannot use time or space, since the functions are not even computable. We cannot use Turing degree, since this notion is not quantitative. Hence we need a new notion of complexity-much like time or spac that is quantitative and yet in some way captures the level of difficulty (such as the Turing degree) of a function."

The last decade has seen parallel developments in computer science and combinatorics, both dealing with networks having strong symmetry properties. Both developments are centred on Cayley graphs: in the design of large interconnection networks, Cayley graphs arise as one of the most frequently used models; on the mathematical side, they play a central role as the prototypes of vertex-transitive graphs. The surveys published here provide an account of these developments, with a strong emphasis on the fruitful interplay of methods from group theory and graph theory that characterises the subject. Topics covered include: combinatorial properties of various hierarchical families of Cayley graphs (fault tolerance, diameter, routing, forwarding indices, etc.); Laplace eigenvalues of graphs and their relations to forwarding problems, isoperimetric properties, partition problems, and random walks on graphs; vertex-transitive graphs of small orders and of orders having few prime factors; distance transitive graphs; isomorphism problems for Cayley graphs of cyclic groups; infinite vertex-transitive graphs (the random graph and generalisations, actions of the automorphisms on ray ends, relations to the growth rate of the graph).

This book features 13 papers presented at the Fifth International Symposium on Recurrence Plots, held August 2013 in Chicago, IL. It examines recent applications and developments in recurrence plots and recurrence quantification analysis (RQA) with special emphasis on biological and cognitive systems and the analysis of coupled systems using cross-recurrence methods. Readers will discover new applications and insights into a range of systems provided by recurrence plot analysis and new theoretical and mathematical developments in recurrence plots. Recurrence plot based analysis is a powerful tool that operates on real-world complex systems that are nonlinear, non-stationary, noisy, of any statistical distribution, free of any particular model type and not particularly long. Quantitative analyses promote the detection of system state changes, synchronized dynamical regimes or classification of system states. The book will be of interest to an interdisciplinary audience of recurrence plot users and researchers interested in time series analysis of complex systems in general.