Digraphs: Theory, Algorithms and Applications [Hardcover]

Jorgen Bang-Jensen (Author), Gregory Gutin (Author)

Book Description

ISBN-10: 1852332689 | ISBN-13: 978-1852332686 | Publication Date: August 6, 2002 | Edition: Corrected

The study of directed graphs has developed enormously over recent decades, yet no book covers more than a tiny fraction of the results from more than 3000 research articles on the topic. Digraphs is the first book to present a unified and comprehensive survey of the subject. In addition to covering the theoretical aspects, including detailed proofs of many important results, the authors present a number of algorithms and applications. The applications of digraphs and their generalizations include among other things recent developments in the Travelling Salesman Problem, genetics and network connectivity. More than 700 exercises and 180 figures will help readers to study the topic while open problems and conjectures will inspire further research.
This book will be essential reading and reference for all graduate students, researchers and professionals in mathematics, operational research, computer science and other areas who are interested in graph theory and its applications.

Editorial Reviews

Review

From the reviews: "Digraphs (directed graphs) are a long-standing and important field of graph theory. Nevertheless, this is the first comprehensive monograph devoted to the subject. As a handbook, it addresses various groups of readers (students as well as researchers, and from various areas of applications). Throughout, because of their importance for applications, emphasis is on algorithms (in form of constructive proofs whenever possible). … a valuable and indispensable reference for many years to come. Readers and users will be thankful!" (P. Schmitt, Monatshefte für Mathematik, Vol. 141 (1), 2004) From the reviews of the second edition: "This is a very comprehensive volume on directed graphs and related topics. … an excellent reference. … the book will be useful not just for researchers focusing on digraphs, but also for everyone … . an extensive list of conjectures and open questions is included in every chapter. These are typically very well presented and easy to understand." (Miklós Bóna, MAA Online, February, 2009) “The first edition of this book was published in 2000 … . The area has continued to develop and this reorganized and updated edition contains an additional six chapters … . there is a strong emphasis on algorithms, and constructive proofs are given whenever possible. There are more than 650 exercises and 150 open problems and conjectures. … the bibliography contains 934 items and the author index contains 740 names. This book would be a valuable resource for anyone interested in digraphs and their applications.” (J. W. Moon, Zentralblatt MATH, Vol. 1170, 2009) --This text refers to the Paperback edition.

From the Back Cover

The theory of directed graphs has developed enormously over recent decades, yet this book (first published in 2000) remains the only book to cover more than a small fraction of the results. New research in the field has made a second edition a necessity. Substantially revised, reorganised and updated, the book now comprises eighteen chapters, carefully arranged in a straightforward and logical manner, with many new results and open problems. As well as covering the theoretical aspects of the subject, with detailed proofs of many important results, the authors present a number of algorithms, and whole chapters are devoted to topics such as branchings, feedback arc and vertex sets, connectivity augmentations, sparse subdigraphs with prescribed connectivity, and also packing, covering and decompositions of digraphs. Throughout the book, there is a strong focus on applications which include quantum mechanics, bioinformatics, embedded computing, and the travelling salesman problem. Detailed indices and topic-oriented chapters ease navigation, and more than 650 exercises, 170 figures and 150 open problems are included to help immerse the reader in all aspects of the subject. Digraphs is an essential, comprehensive reference for undergraduate and graduate students, and researchers in mathematics, operations research and computer science. It will also prove invaluable to specialists in related areas, such as meteorology, physics and computational biology. Jørgen Bang-Jensen is a Professor in the Department of Mathematics and Computer Science at the University of Southern Denmark, Odense, Denmark. Gregory Gutin is Professor of Computer Science at Royal Holloway College, University of London, UK. --This text refers to the Paperback edition.

Product Details

• Hardcover: 754 pages
• Publisher: Springer; Corrected edition (August 6, 2002)
• Language: English
• ISBN-10: 1852332689
• ISBN-13: 978-1852332686
• Product Dimensions: 9.4 x 6.4 x 1.8 inches
• Shipping Weight: 2.8 pounds
• Average Customer Review: 4.0 out of 5 stars  See all reviews (2 customer reviews)
• Amazon Best Sellers Rank: #4,881,058 in Books (See Top 100 in Books)

More About the Author

Discover books, learn about writers, read author blogs, and more.

Customer Reviews

Most Helpful Customer Reviews

19 of 20 people found the following review helpful:

5.0 out of 5 stars Directed graphs are more general than undirected graphs, May 9, 2001

By 

[e-mail] (Groningen, The Netherlands) - See all my reviews

This review is from: Digraphs: Theory, Algorithms and Applications (Hardcover)

This book reflects the main achievements of the last three decades in the directed graphs theory as well as many applications including combinatorial optimization, operations research and the fascinating area of mathematics and computer science called discrete mathematics. Since the monograph contents are given, I do not wish to go into details of material presented there. Instead I'd like to discuss the aims of the book as well as who could be its readers.

The text strives to accomplish the following objectives:

1. To give a great deal of information on both results and proof techniques for specialists in graph theory. No other book covers even 10\% of material provided in Digraphs, and thus before this monograph has been published even specialists in graph theory very often needed to search for a specific result or proof technique through the ocean of literature on digraphs. Now the situation has drastically improved.

2. To introduce researchers and practitioners from various other fields in mathematics, computer science, operations research, biology, etc. to basic and more advanced results in digraph theory and algorithms and some carefully selected applications. It offers much more than merely a pure bibliography and provides the ideal starting point for any researcher who needs to become familiar either with theory oriented aspects of this interesting area or with some application in a relatively short time.

3. To provide enough material for intermediate and final year BSc or MSc courses for students in mathematics, computer science and operations research. The large number of exercises (more than 700) of various difficulty is of great help to instructors and lecturers. The applications provided in the book will help to provide enough motivation for the students to study digraph theory and algorithms.

4. To provide a large variety of topics for final year student projects in mathematics, computer science, operations research and other fields. The monograph can be used as a source for the projects because because several areas of digraph theory are covered there in real depth and they vary from relatively simple to reasonably complicated ones.

To summarize, I'd like to notice that the monograph is aimed to a wide range of readers including specialists in mathematics, operations research, computer science, biology, etc. as well as students of second year and higher.

Boris Goldengorin, Department of Econometrics and Operations Research, University of Groningen, The Netherlands

6 of 6 people found the following review helpful:

3.0 out of 5 stars Good for experts and researchers but not for beginners, July 24, 2007

By 

KONG Chi Leung (Hong Kong) - See all my reviews
(REAL NAME)   

This review is from: Digraphs: Theory, Algorithms and Applications (Hardcover)

I come across this book when finding relevant materials of graph theory. As told by previous reviewer, this book contains much recent research results and is good for experts or researchers. The preface says that it is suitable for undergraduate, but in my feeling, you need to be a graduate with a full year course of graph theory completed to understand or utilize the materials of the book. The materials are presented in a standard theorem-proof format, one theorem after another. Examples are few. Though the book title contains "Algorithm", there are also few algorithms presented in the form you saw in books of computing. Probably you need to design your own algorithm after digesting the material. Besides, exercises are abundant but no hints or answers provided.