logo资料库

书 [Ravindra_K._Ahuja,_Thomas_L._Magnanti,_James_B._O_Network_Flo....pdf

发布时间：2022-06-09 发布人：admin 分类：说明书 资料大小：19.16M 资料格式：pdf 举报 版权申诉
第1页 / 共863页
第2页 / 共863页
第3页 / 共863页
第4页 / 共863页
第5页 / 共863页
第6页 / 共863页
第7页 / 共863页
第8页 / 共863页
资料共863页，剩余部分请下载后查看
    NETWORK FLOWS Theory, Algorithms, and Applications BA VINDRA K. AHUJA Department of Industrial & Management Engineering Indian Institute of Technology, Kanpur THOMAS L. MAGNANT! Sloan School of Management Massachusetts Institute of Technology, Cambridge JAMES B. ORLIN Sloan School of Management Massachusetts Institute of Technology, Cambridge PRENTICE HALL, Upper Saddle River, New Iersey 07458
    Library of Congress Cataloging-in-Publication Data Ahuja, Ravindra K. (date) Network flows: theory, algorithms, and applications I Ravindra K. Ahuja, Thomas L. Magnantl. James B. Orlin. p. cm. Includes bibliographical references and index. ISBN 0-13-6J7S49-X I. Network analysis (Planning) 2. Mathematical optimization. III. Title. II. Orlin. James B .. (datel. I. Magnanti, Thomas L. TS7.SS.A37 1993 6SS.4'032-dc20 92-26702 CIP Acquisitions editor: Pete Janzow Production editor: Merrill Peterson Cover designer: Design Source Prepress buyer: Linda Behrens Manufacturing buyer: David Dickey Editorial assistant: Phyllis Morgan The author and publisher of this book have used their best efforts in preparing this book. These effort! include the development, research, and testing of the theories and programs to determine their effectiveness. The author and publisher make no warranty of any kind, expressed or implied, with regard to these programs or the documentation contained in this book. The author and publisher shaH not be liable in any event for incidental or consequential damages in connection with, or arising out of the furnishing, performance, or use of these Drograms. C 1993 by Prentice-Hall, Inc. Upper Saddle River. New Jeney 074S8 All rights reserved. No part of this book may be reproduced, in any form or by any means, without permission in writing from the publisher. Printed in the United States of America 16 17 18 19 ISBN 0-13-617S49-X PRENTICE-HALL INTERNATIONAL (UK) LIMITED, London PRENTICE-HALL OF AUSTRALIA PrY. LIMITED, Sydney PRENTICE-HALL CANADA INC., Toronto PRENTICE-HALL HISPANOAMERICANA, S.A., Mexico PRENTICE-HALL OF INDIA PRIVATE LIMITED, New Delhi PRENTICE-HALL OF JAPAN, INC., Tokyo EDITORA PRENTICE-HALL DO BRASIL, LTDA., Rio de Janeiro
    Ravi dedicates this book to his spiritual master, Revered Sri Ranaji Saheb. Tom dedicates this book to his favorite network, Beverly and Randy. Jim dedicates this book to Donna, who inspired him in so many ways. Collectively, we offer this book as a tribute to Lester Ford and Ray Fulkerson, whose pioneering research and seminal text in network flows have been an enduring inspiration to us and to a generation of researchers and practitioners.
    CONTENTS PREFACE, xl 1 INTRODUCTION, 1 1.1 Introduction, 1 Network Flow Problems, 4 1.2 Applications, 9 1.3 Summary, 18 1.4 Reference Notes, 19 Exercises, 20 2 PATHS, TREES, AND CYCLES, 23 2.1 2.2 2.3 2.4 2.5 Introduction, 23 Notation and Definitions, 24 Network Representations, 31 Network Transformations, 38 Summary, 46 Reference Notes, 47 Exercises, 47 3 ALGOlUTHM DESIGN AND ANALYSIS, ~3 3.1 3.2 3.3 3.4 3.5 3.6 Introduction, 53 Complexity Analysis, 56 Developing Polynomial-Time Algorithms, 66 Search Algorithms, 73 Flow Decomposition Algorithms, 79 Summary, 84 Reference Notes, 85 Exercises, 86 4 SHORTEST PA THS: LABEL-SETTING ALGOBITHMS, 93 4.1 4.2 4.3 4.4 4.5 4.6 4.7 4.8 Introduction, 93 Applications, 97 Tree of Shortest Paths, 106 Shortest Path Problems in Acyclic Networks, 107 Dijkstra's Algorithm, 108 Dial's Implementation, 113 Heap Implementations, 115 Radix Heap Implementation, 116 v
    4.9 Summary, 121 Reference Notes, 122 Exercises, 124 15 SHORTEST PATHS: LABEL-COBBECTING ALGOBITHMS, 133 Introduction, 133 Optimality Conditions, 135 Generic Label-Correcting Algorithms, 136 Special Implementations of the Modified Label-Correcting Algorithm, 141 Detecting Negative Cycles, 143 All-Pairs Shortest Path Problem, 144 5.1 5.2 5.3 5.4 5.5 5.6 5.7 Minimum Cost-to-Time Ratio Cycle Problem, 150 5.8 Summary, 154 Reference Notes, 156 Exercises, 157 8 MAXIMUM FLOWS: BABIC IDEAS, 188 6.1 6.2 6.3 6.4 6.5 6.6 6.7 6.8 Introduction, 166 Applications, 169 Flows and Cuts, 177 Generic Augmenting Path Algorithm, 180 Labeling Algorithm and the Max-Flow Min-Cut Theorem, 184 Combinatorial Implications of the Max-Flow Min-Cut Theorem, 188 Flows with Lower Bounds, 191 Summary, 196 Reference Notes, 197 Exercises, 198 7 MAXIMUM FLOWS: POLYNOMIAL ALGOBITHMB, 207 Introduction, 207 Distance Labels, 209 Capacity Scaling Algorithm, 210 Shortest Augmenting Path Algorithm, 213 Distance Labels and Layered Networks, 221 Generic Preflow-Push Algorithm, 223 FIFO Preflow-Push Algorithm, 231 Highest-Label Preflow-Push Algorithm, 233 Excess Scaling Algorithm, 237 7.1 7.2 7.3 7.4 7.5 7.6 7.7 7.8 7.9 7.10 Summary, 241 Reference Notes, 241 Exercises, 243 8 MAXIMUM FLOWS: ADDITIONAL TOPICS, 2lJO Introduction, 250 Flows in Unit Capacity Networks, 252 Flows in Bipartite Networks, 255 Flows in Planar Undirected Networks, 260 Dynamic Tree Implementations, 265 8.1 8.2 8.3 8.4 8.5 vi Contents
    8.6 8.7 8.8 Network Connectivity, 273 All-Pairs Minimum Value Cut Problem, 277 Summary, 285 Reference Notes, 287 Exercises, 288 9 MINIMUM COST FLOWS: BABIC ALGOBITHMS, 294 Introducti"on, 294 Applications, 298 Optimality Conditions, 306 9.1 9.2 9.3 9.4 Minimum Cost Flow Duality, 310 9.5 9.6 9.7 9.8 9.9 9.10 Relaxation Algorithm, 332 9.11 9.12 Summary, 339 Relating Optimal Flows to Optimal Node Potentials, 315 Cycle-Canceling Algorithm and the Integrality Property, 317 Successive Shortest Path Algorithm, 320 Primal-Dual Algorithm, 324 Out-of-Kilter Algorithm, 326 Sensitivity Analysis, 337 Reference Notes, 341 Exercises, 344 10 MINIMUM COST FLOWS: POLYNOMIAL ALGORITHMS, 8lJ7 Introduction, 357 Capacity Scaling Algorithm, 360 Cost Scaling Algorithm, 362 Double Scaling Algorithm, 373 10.1 10.2 10.3 10.4 10.5 Minimum Mean Cycle-Canceling Algorithm, 376 10.6 10.7 10.8 Repeated Capacity Scaling Algorithm, 382 Enhanced Capacity Scaling Algorithm, 387 Summary, 395 Reference Notes, 396 Exercises, 397 11 MINIMUM COST FLOWS: NETWORK SIMPLEX ALGO.RlTHMS, 402 Introduction, 402 Cycle Free and Spanning Tree Solutions, 405 11.1 11.2 11.3 Maintaining a Spanning Tree Structure, 409 Computing Node Potentials and Flows, 411 11.4 11. 5 Network Simplex Algorithm, 415 Strongly Feasible Spanning Trees, 421 11.6 Network Simplex Algorithm for the Shortest Path Problem, 425 11.7 Network Simplex Algorithm for the Maximum Flow Problem, 430 11.8 11.9 Related Network Simplex Algorithms, 433 11.10 Sensitivity Analysis, 439 11.11 Relationship to Simplex Method, 441 11.12 U nimodularity Property, 447 11.13 Summary, 450 Reference Notes, 451 Exercises, 453 Contents vii
    分享到：
    赞 收藏

    相关推荐

    资料库

    课程资源

    共收录17145份资料，累计13个分类，关注成员有19位，主要包括：PHP,网络管理,网页制作,Java,.Net,数据库,3G/移动开发,C/C++,游戏开发,嵌入式,讲义,软件测试,专业指导

    热门标签

    PHP 网络管理 网页制作 Java .Net 数据库 3G/移动开发 C/C++ 游戏开发 嵌入式 讲义 软件测试 专业指导

    最新资料