Название: Topics in Algorithmic Graph Theory
Автор: Lowell W. Beineke, Martin Charles Golumbic
Издательство: Cambridge University Press
Серия: Encyclopedia of Mathematics and its Applications
Год: 2021
Страниц: 361
Язык: английский
Формат: pdf (true)
Размер: 10.2 MB

Algorithmic graph theory has been expanding at an extremely rapid rate since the middle of the twentieth century, in parallel with the growth of Computer Science and the accompanying utilization of computers, where efficient algorithms have been a prime goal. This book presents material on developments on graph algorithms and related concepts that will be of value to both mathematicians and computer scientists, at a level suitable for graduate students, researchers and instructors. The fifteen expository chapters, written by acknowledged international experts on their subjects, focus on the application of algorithms to solve particular problems. All chapters were carefully edited to enhance readability and standardize the chapter structure as well as the terminology and notation. The editors provide basic background material in graph theory, and a chapter written by the book's Academic Consultant, Martin Charles Golumbic (University of Haifa, Israel), provides background material on algorithms as connected with graph theory.

Chapter 1 opens with a review of basic graph algorithms, including graph search and greedy colouring, leading to applications on structured graph classes. Results on planar graphs and special classes of intersection graphs are featured. Exploiting graph structure is one of the fundamental approaches for designing efficient algorithms to solve important practical problems, and this theme repeats itself in many chapters of this book.

In Chapter 2 present three graph colouring variations – selective colouring, online colouring, and mixed graph colouring – and motivating applications, complexity results and algorithmic developments are discussed for each variation. Chapter 3 is a survey of total colouring, where we assign a colour to each vertex and edge of a graph so that there are no incidence colour conflicts. Both theoretical and algorithmic results are considered for this alternative colouring problem.

In Chapter 4 focuses on models and efficient algorithms for testing graph properties. This is the study of deciding the existence of a property in time or space that is significantly smaller than the size of the input, while trading off the accuracy. Property testing has potential applications to ‘Big Data’ scenarios.
...
Chapter 14 surveys the basic properties of sparse classes of graphs, from structural, algorithmic and model-theoretic points of view. Finally, in Chapter 15, Serge Gaspers considers extremal vertex-sets in graphs. For a property P, the extremal vertex-sets are either the inclusion-wise minimal or the inclusion-wise maximal vertex-sets with property P. This chapter establishes bounds on the largest number of such extremal vertex-sets that a graph may have, and discusses enumeration algorithms and their use in exponential-time algorithms.

These 15 original chapters, presented here for the first time, are advanced education-oriented surveys, each starting with a familiar theme and developing it through many of the latest results. For those who wish to read more about the topics in books and papers, the references provide many pointers to further reading on aspects that one cannot find in textbooks.