Programming in Networks and Graphs On the Combinatorial Background a
Network flow and matching are often treated separately in the literature and for each class a variety of different algorithms has been developed. These algorithms are usually classified as primal, dual, primal-dual etc. The question the author addresses i
- PDF / 19,058,627 Bytes
- 323 Pages / 430.866 x 649.134 pts Page_size
- 69 Downloads / 158 Views
Ulrich Derigs
Programming in Networks and Graphs On the Combinatorial Background and Near-Equivalence of Network Flow and Matching Algorithms
Lectu re Notes in Economics and Mathematical Systems Managing Editors: M. Beckmann and W. Krelle
300 Ulrich Derigs
Programming in Networks and Graphs On the Combinatorial Background and Near-Equivalence of Network Flow and Matching Algorithms
Springer-Verlag Berlin Heidelberg GmbH
Editorial Board
H. Albach M. Beckmann (Managing Editor) P.Ohrymes G. Fandel G. Feichtinger J. Green W.Hildenbrand W. Krelle (Managing Editor) H.P.Klinzi K. Ritter R.Sato U.Schittko P. Schonfeld R.Selten Managing Editors Prof. Dr. M. Beckmann Brown University Providence, RI 02912, USA Prof. Dr. W. Krelle Institut fi.ir Gesellschafts- und Wirtschaftswissenschaften der Universitat Bonn Adenauerallee 24-42, 0-5300 Bonn, FRG Author Prof. Dr. Dr. Ulrich Oerigs Lehrstuhl fUr Betriebswirtschaftslehre, insbesondere Betriebsinformatik Universitiit Bayreuth, Universitiitsstr. 30, 0·8580 Bayreuth, FRG
ISBN 978-3-540-18969-5 ISBN 978-3-642-51713-6 (eBook) DOI 10.1007/978-3-642-51713-6 library of Congress Catalcqinq-in-Publication Data. Derigs , Ulrich, 1950- Programming in networks and graphs . (Lecture notes in economics and mathematical systems ; 300) Bibliography: p. 1. Combinatorial optimization. 2. Network analysis (Planning) 3. Matching theory . I. Title. II. Series . QA402.5.D47 1988511'.688-3163 This work is subject to copyright. All rights are reserved . whethe r the whole or part of the material is concerned. specifically the rights of translation. reprinting . re-use of illustrations, recitat ion, broadcasting . rep roduction on microfilms or in other ways, and storage in data banks . Duplication of this publication or parts thereof is only permitted under the provisions of the German Copyright Law of September 9 . 1965. in its version of June 24, 1985. and a copyright fee must always be paid. Violations fall under the prosecution act of the German Copyright Law .
© Springer-Verlag Berlin Heidelberg 1988 Originally published by Spr inger-Verlag Berlin Heidelberg New York in 1988 2142/3140·543210
Meinen Eltern in Dankbarkeit gewidmet
C'est le temps que tu as perdu pour ta rose qui fait ta rose si importante. ( A. de Sainte Exupery )
Preface
Since the origins of combinatorial optimization network flow-, matchingand certain matroid problems have been treated as cornerstone problems of this discipline. For each of these problems a variety of algorithms was developed which were able to solve even large-scale, real-world problems. This last property made these classes outstanding and attractive. During the seventies with the development of the "complexity theory" of computer algorithms the uni verse of combinatorial optimization problems was divided into two major classes: the "easy" problems (Le. those for which a polynomial algorithm was known) and the "hard" problems (Le. the so-called NP-complete problems which all become easy if the existence of a polynomial algorithm for only one repr
Data Loading...
