Fast Parallel Algorithms for Graph Matching Problems

by Marek Karpinski, Wojciech Rytter

Overview

The matching problem is central to graph theory and the theory of algorithms. This book provides a comprehensive and straightforward introduction to the basic methods for designing efficient parallel algorithms for graph matching problems. Written for students at the beginning graduate level, the exposition is largely self-contained and example-driven; prerequisites have been kept to a minimum by including relevant background material. The book contains full details of several new techniques and will be of interest to researchers in computer science, operations research, discrete mathematics, and electrical engineering. The main theoretical tools are presented in three independent chapters, devoted to combinatorial tools, probabilistic tools, and algebraic tools. One of the goals of the book is to show how these three approaches can be combined to develop efficient parallel algorithms. The book represents a meeting point of interesting algorithmic techniques and opens up new algebraic and geometric areas.

Product Details

ISBN-13:	9780198501626
Publisher:	Oxford University Press
Publication date:	05/28/1998
Series:	Oxford Lecture Series in Mathematics and Its Applications , #9
Pages:	224
Product dimensions:	6.30(w) x 9.30(h) x 0.80(d)

About the Author

University of Bonn

University of Liverpool

Table of Contents

Contents List - Page 1Preface1. Introduction2. Combinatorial tools3. Three sequential algorithms4. Probabilistic tools5. Algebraic tools6. Maximum cardinality polynomials7. Inclusion maximal matchings8. Maximal independent sets9. Four easy subclasses of graphs10. Convex bipartite graphs11. f-Matchings12. Parallelization of sequential algorithms13. Pfaffians, counting the number of matchings, and planar graphs14. Basic applications of matchings to other problems15. More applicationsBibliography