K. Erciyes - Algebraic Graph Algorithms: A Practical Guide Using Python (Undergraduate Topics in Computer Science)

Undergraduate Topics in Computer Science (UTiCS) delivers high-quality instructional content for undergraduates studying in all areas of computing and information science. From core foundational and theoretical material to final-year topics and applications, UTiCS books take a fresh, concise, and modern approach and are ideal for self-study or for a one- or two-semester course. The texts are all authored by established experts in their fields, reviewed by an international advisory board, and contain numerous examples and problems, many of which include fully worked solutions.

The UTiCS concept relies on high-quality, concise books in softback format, and generally a maximum of 275300 pages. For undergraduate textbooks that are likely to be longer, more expository, Springer continues to offer the highly regarded Texts in Computer Science series, to which we refer potential authors.

More information about this series at https://link.springer.com/bookseries/7592

This Springer imprint is published by the registered company Springer Nature Switzerland AG

The registered company address is: Gewerbestrasse 11, 6330 Cham, Switzerland

Graphs are discrete structures that find many applications such as modeling computer networks, social networks and biological networks. Graph theory is centered around studying graphs and there has been an unprecedented growth in this branch of mathematics over the last few decades, mainly due to the realization of numerous applications of graphs in real-life.

This book is about the design and analysis of algebraic algorithms to solve graph problems. The algebraic way of analyzing graph problems can be viewed from the angles of group theory and linear algebra. We will mostly use linear algebraic methods which commonly make use of matrices associated with graphs in search of suitable graph algorithms. There are few benefits to be gained by this approach; first of all, many results from matrix algebra theory become readily available, for matrix analysis of graphs. Secondly, various matrix algorithms such as matrix multiplication are readily available, enabling easiness in coding. Moreover, methods for parallel matrix computations are well known and various libraries for this purpose are available which provides a convenient way for parallelizing the algorithms.

The algebraic nature of graphs is a vast theoretical topic with many new and frequent results. For this reason, the level of exposure required careful consideration while forming the detailed topics of the book. At one end; we have rich, resourceful and sometimes quite complicated matrix algebra theory that can be used in the analysis of graphs which does not always result in practical graph algorithms; and at the other extreme, one can frequently devise an algebraic version of a classical graph algorithm by using the matrices that represent graphs. We tried to stay somewhere in between by reviewing main algebraic results that are useful in designing practical graph algorithms and on the other hand, mostly using graph matrices to solve graph problems. The extent of exposure to parallel processing was another decision and after briefly reviewing the basic theory on parallel processing, we provide practical hints for parallel processing associated with algebraic algorithms where possible. Matrix multiplication is at the core of majority of algebraic graph algorithms and any such algorithm may be parallelized conveniently, at least partly, using parallel matrix multiplication methods we describe. Thus, obtaining parallel version of the algorithms reviewed becomes a trivial task in most cases. In summary, the focus of the book is on practical algebraic graph algorithms using results from matrix algebra rather than algebraic study of graphs.

The intended audience for this book is the senior/graduate students of computer science, electrical and electronic engineering, bioinformatics, and any researcher or a person with background in discrete mathematics, basic graph theory and algorithms. There is a Web page for the book to keep errata Python code and other material at: http://ube.ege.edu.tr/~erciyes/AGA/erciyes/AGA/ .

Python Implementation

For almost all algorithms, we provide Python programming language code that can be modified and tested for various inputs. Python is selected for its simplicity, efficiency and rich library routines and hence the name of the book. The code for an algorithm is not optimized and brevity is forsaken for clarity in many cases. In various algorithms, we use different data structures and methods for similar problems to show alternative implementations. The codes are tested for various sample graphs, however; as it frequently happens with any software, errors are possible and I would be happy to know any bugs by e-mail at kayhanerayes@maltepe.edu.tr.