Skip to main content
SpringerLink
Log in

Combinatorial Optimization

Theory and Algorithms

  • Textbook
  • © 2002

Overview

Authors:
  1. Bernhard Korte

    1. Research Institute for Discrete Mathematics, University of Bonn, Bonn, Germany

    View author publications

    You can also search for this author in PubMed   Google Scholar

  2. Jens Vygen

    1. Research Institute for Discrete Mathematics, University of Bonn, Bonn, Germany

    View author publications

    You can also search for this author in PubMed   Google Scholar

  • Well-written textbook on combinatorial optimization
  • One of very few textbooks on this topic
  • Subject area has manifold applications
  • Includes supplementary material: sn.pub/extras

Part of the book series: Algorithms and Combinatorics (AC, volume 21)

This is a preview of subscription content, log in via an institution to check access.

Access this book

Log in via an institution
eBook USD 74.99
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever

Tax calculation will be finalised at checkout

Other ways to access

Licence this eBook for your library

Institutional subscriptions

Table of contents (21 chapters)

  1. Front Matter

    Pages I-XIII
    Download chapter PDF

  2. Introduction

    • Bernhard Korte, Jens Vygen
    Pages 1-12

  3. Graphs

    • Bernhard Korte, Jens Vygen
    Pages 13-47

  4. Linear Programming

    • Bernhard Korte, Jens Vygen
    Pages 49-64

  5. Linear Programming Algorithms

    • Bernhard Korte, Jens Vygen
    Pages 65-90

  6. Integer Programming

    • Bernhard Korte, Jens Vygen
    Pages 91-116

  7. Spanning Trees and Arborescences

    • Bernhard Korte, Jens Vygen
    Pages 117-137

  8. Shortest Paths

    • Bernhard Korte, Jens Vygen
    Pages 139-152

  9. Network Flows

    • Bernhard Korte, Jens Vygen
    Pages 153-184

  10. Minimum Cost Flows

    • Bernhard Korte, Jens Vygen
    Pages 185-204

  11. Maximum Matchings

    • Bernhard Korte, Jens Vygen
    Pages 205-233

  12. Weighted Matching

    • Bernhard Korte, Jens Vygen
    Pages 235-260

  13. b-Matchings and T-Joins

    • Bernhard Korte, Jens Vygen
    Pages 261-278

  14. Matroids

    • Bernhard Korte, Jens Vygen
    Pages 279-309

  15. Generalizations of Matroids

    • Bernhard Korte, Jens Vygen
    Pages 311-326

  16. NP-Completeness

    • Bernhard Korte, Jens Vygen
    Pages 327-359

  17. Approximation Algorithms

    • Bernhard Korte, Jens Vygen
    Pages 361-396

  18. The Knapsack Problem

    • Bernhard Korte, Jens Vygen
    Pages 397-406

  19. Bin-Packing

    • Bernhard Korte, Jens Vygen
    Pages 407-422

  20. Multicommodity Flows and Edge-Disjoint Paths

    • Bernhard Korte, Jens Vygen
    Pages 423-444
Back to top

Keywords

About this book

It was more than a surprise to us that the first edition of this book already went out of print about a year after its first appearance. We were flattered by the many positive and even enthusiastic comments and letters from colleagues and the gen­ eral readership. Several of our colleagues helped us in finding typographical and other errors. In particular, we thank Ulrich Brenner, Andras Frank, Bernd Gartner and Rolf Mohring. Of course, all errors detected so far have been corrected in this second edition, and references have been updated. Moreover, the first preface had a flaw. We listed all individuals who helped us in preparing this book. But we forgot to mention the institutional support, for which we make amends here. It is evident that a book project which took seven years benefited from many different grants. We would like to mention explicitly the bilateral Hungarian­ German Research Project, sponsored by the Hungarian Academy of Sciences and the Deutsche Forschungsgemeinschaft, two Sonderforschungsbereiche (special re­ search units) of the Deutsche Forschungsgemeinschaft, the Ministere Franc;ais de la Recherche et de la Technologie and the Alexander von Humboldt Foundation for support via the Prix Alexandre de Humboldt, and the Commission of the Eu­ ropean Communities for participation in two projects DONET. Our most sincere thanks go to the Union of the German Academies of Sciences and Humanities and to the Northrhine-Westphalian Academy of Sciences.

Reviews

From the reviews of the 2nd Edition:

"Provides a useful collection of the major techniques, results and references in combinatorial optimization for researchers and teachers in the field."—

MATHEMATICAL REVIEWS

"This book on combinatorial optimization is a beautiful example of the ideal textbook."

Operations Resarch Letters 33 (2005), p.216-217

"The second edition (with corrections and many updates) of this very recommendable book documents the relevant knowledge on combinatorial optimization and records those problems and algorithms that define this discipline today. To read this is very stimulating for all the researchers, practitioners, and students interested in combinatorial optimization."

OR News 19 (2003), p.42

From the reviews of the third edition:

"In the last years Korte and J. Vygen’s ‘Combinational Optimization. Theory and Algorithms’ has become a standard textbook in the field. 5 years after the first edition … the 3rd revised edition is available. … several proofs have been streamlined, the references have been updated and new exercises have been added. That makes this volume to one of the most comprehensive and up-to-date textbooks in the field of combinatorial optimization."

Rainer E. Burkard, Zentralblatt MATH, Vol. 1099 (1), 2007

"This volume is an encyclopedic reference and textbook on theory and algorithms in combinatorial optimization. … As befits a reference book, the references are very complete and up to date. … The book has separate topic and author indexes and a very useful glossary of notation. … The book … will appeal primarily to readers who want an advanced textbook that can also serve as a concise reference. … The current volume by Korte and Vygen is a worthy successor."

Brian Borchers, MathDL, May, 2006

Authors and Affiliations

  • Research Institute for Discrete Mathematics, University of Bonn, Bonn, Germany

    Bernhard Korte, Jens Vygen

Bibliographic Information

Publish with us

Policies and ethics

Back to top

Search

Navigation