- Series: Oxford Lecture Series in Mathematics and Its Applications (Book 31)
- Hardcover: 640 pages
- Publisher: Oxford University Press; 1 edition (June 1, 2011)
- Language: English
- ISBN-10: 0199205272
- ISBN-13: 978-0199205271
- Product Dimensions: 9.3 x 1.6 x 6.1 inches
- Shipping Weight: 2.4 pounds (View shipping rates and policies)
- Average Customer Review: 4.0 out of 5 stars See all reviews (1 customer review)
- Amazon Best Sellers Rank: #1,657,807 in Books (See Top 100 in Books)
Enter your mobile number or email address below and we'll send you a link to download the free Kindle App. Then you can start reading Kindle books on your smartphone, tablet, or computer - no Kindle device required.
To get the free app, enter your mobile phone number.
Connections in Combinatorial Optimization (Oxford Lecture Series in Mathematics and Its Applications) 1st Edition
Use the Amazon App to scan ISBNs and compare prices.
The Amazon Book Review
Author interviews, book reviews, editors picks, and more. Read it now
"The title of the book is wisely chosen: it deals, among other subjects, with graph connectivity, and it provides connections between graph theoretical results and underlying combinatorial structures...The book is readable for students, researchers, possibly also practitioners." -- Mathematical Reviews
About the Author
Andras Frank is the founder and head of the MTA-ELTE Egervary Research Group (EGRES) at Eotvos University. He was head of the Department of Operations Research at Eotvos University between 2005 and 2009. In 2002, he was awarded the Tibor Szele Prize by the Janos Bolyai Mathematical Society.
Browse award-winning titles. See more
If you are a seller for this product, would you like to suggest updates through seller support?
Top Customer Reviews
by Andras Frank
Oxford University Press, Oxford, 2011.
(Disclaimer: I have read some parts of the book in detail, and have skimmed over other parts. Thus, this review is based on
incomplete information; but, if I wait till I have studied all of the book, then the review may be delayed for far too long.)
Combinatorial Optimization (CO) is a vibrant area within the mathematical sciences with close ties to areas such as
Algorithms, Computational Complexity, Graph Theory, Mathematical Programming, and Operations Research. CO is built on some simple and powerful ideas and the interactions between them.
The book has three parts. Part 1 of the book, Chapters 1-5, gives an
elegant introduction to the core of CO including connectivity, paths
and bipartite matchings, network flows, polyhedral combinatorics, and
matroid theory. This part is valuable for all teachers and students of
CO. The presentation focuses on the fundamentals and gives a concise,
elegant development of these core topics. The author uses his own
perspective, and this adds to the charm. To mention one item: a
theorem on orienting the edges of a graph to meet degree requirements
is proved via the push-relabel flow algorithm of Goldberg and Tarjan
(Theorem 2.3.5, pp.60-63).
Part 2, Chapters 6-11, covers algorithms for flows and cuts, the
structure and representation of cuts, the splitting-off operation,
orientation of graphs, packing and covering of trees and arborescences,
and connectivity augmentation.
Part 3, Chapters 12-17, covers submodular optimization and extensions,
including matroid optimization, generalized polymatroids, submodular
functions, and covering supermodular functions by digraphs.
The author is one of the world's leading researchers in CO, and one of his long-term goals is to bring the big theorems to the people.
Those wishing to know more about the book should read the preface (freely accessible at the website of the publisher: Oxford University Press); it has a comprehensive discussion of the contents and the aims of the author.
Every book in mathematics has to strike a balance between the aim of
communicating core ideas simply and directly, and the level of rigour.
The author has opted for a rigorous presentation. The advantage of
this is the precision and the ability to fully harness the power of
formalisms and abstractions. But this means that readers new to the area
have to invest some time to master the notation.
Here are a couple of comments for the author/publisher: Is it possible
for the publisher to make a free PDF copy of the book available for
downloading? This feature is being used by some recent books, e.g.,
Diestel's "Graph Theory", and Williamson and Shmoys' "The Design of
Approximation Algorithms". A shorter and simpler version of the book,
based on Chapters 1-5 and aimed at undergraduate students, could serve
as an attractive introduction to CO.
This book gives an elegant and precise coverage of some important
topics of CO. The coverage in Chapters 1-5 (Part 1) could serve the
needs of an introductory graduate course. Besides presenting some of
the key methods in the area, the book develops and explains abstract
submodular results. Everyone who teaches courses in CO will benefit
from this book. Moreover, the book is valuable for researchers and
Ph.D. level students working in CO and in areas related to CO, such as
Approximation Algorithms, Algorithmic Game Theory and Mechanism Design,
Learning Theory, Mathematical Programming, and Operations Research.
It seems appropriate to conclude by recalling an incident from more
than 80 years ago, pertaining to the birth of the subject of
Connectivity. In the spring of 1930, the mathematician Karl Menger
visited Budapest, and met Denes Konig. Menger described to Konig his
n-arc theorem (similar to Theorem 2.5.8 in this book). Konig was
interested, but did not believe this. "This evening" he said to Menger
"I won't go to sleep before having constructed a counterexample." The
next day, Konig admitted that he had had a sleepless night. Later on,
Konig added this theorem to his book "Theorie der endlichen and
unendlichen Graphen" (1936), and it is now regarded as the key theorem
of Connectivity. (K.Menger, J. Graph Theory 5 (1981) 341-350, "On the
origin of the n-arc theorem.")