It has arisen as the basis of several courses on combinatorial optimization and more special topics at graduate level. Since the complete book contains enough material for at least four semesters (4 hours a week), one usually selects material in a suitable way.
The book contains complete (but concise) proofs, also for many deep results, some of which did not appear in a book before. Many very recent topics are covered as well, and many references are provided. Thus this book represents the state-of-the-art of combinatorial optimization.
Algorithms and Combinatorics 21
Editorial Board R.L. Graham, La Jolla B. Korte, Bonn L. Lovász, Budapest A. Wigderson, Princeton G.M. Ziegler, Berlin
Bernhard Korte Jens Vygen
Combinatorial Optimization Theory and Algorithms Third Edition
123
Bernhard Korte Jens Vygen Research Institute for Discrete Mathematics University of Bonn Lennéstraße 2 53113 Bonn, Germany e-mail:
[email protected] [email protected]
Library of Congress Control Number: 2005931374
Mathematics Subject Classification (2000): 90C27, 68R10, 05C85, 68Q25 ISSN 0937-5511 ISBN-10 3-540-25684-9 Springer-Verlag Berlin Heidelberg New York ISBN-13 978-3-540-25684-7 Springer-Verlag Berlin Heidelberg New York ISBN 3-540-43154-3 2nd ed. Springer-Verlag Berlin Heidelberg New York This work is subject to copyright. All rights are reserved, whether the whole or part of the material is conce