Data Structures and Network Algorithms.pdf

发布时间：2022-06-08 发布人：admin 分类：说明书资料大小：12.82M 资料格式：pdf 举报版权申诉

bigarm-8792663-4744302543346820027.pdf-第1页.png

第1页 / 共142页

bigarm-8792663-4744302543346820027.pdf-第2页.png

第2页 / 共142页

bigarm-8792663-4744302543346820027.pdf-第3页.png

第3页 / 共142页

bigarm-8792663-4744302543346820027.pdf-第4页.png

第4页 / 共142页

bigarm-8792663-4744302543346820027.pdf-第5页.png

第5页 / 共142页

bigarm-8792663-4744302543346820027.pdf-第6页.png

第6页 / 共142页

bigarm-8792663-4744302543346820027.pdf-第7页.png

第7页 / 共142页

bigarm-8792663-4744302543346820027.pdf-第8页.png

第8页 / 共142页

文本预览

CBMS-NSF REGIONAL CONFERENCE SERIES IN APPLIED MATHEMATICS A series of lectures on topics of current research interest in applied mathematics under the direction of the Conference Board of the Mathematical Sciences, supported by the National Science Foundation and published by SIAM. I.VISLI -y. Weak Convergence of Measures: Applications in Probability G A K R HT BiRKiion , The Numerical Solution of Elliptic Equations D. V. L I N D I Y, Bayesian Statistics, A Review R S. VAR<;A. Functional Analysis and Approximation Theory in Numerical Analysis R R H : \ I I \ D I : R, Some Limit Theorems in Statistics P X I KK K Bin .1. I.. LIONS. Some Aspects of the Optimal Control of Distributed Parameter Systems R ( H ; I :R PI-NROSI-:. Tecltniques of Differentia/ Topology in Relativity Hi.KM \N C'ui KNOI r. Sequential Analysis and Optimal Design .1. D I ' K H I N. Distribution Theory for Tests Based on the Sample Distribution Function Soi I. Ri BINO\\, Mathematical Problems in the Biological Sciences P. D. L \ x. Hyperbolic Systems of Conservation Laws and the Mathematical Theory of Shock Waves I. .1. Soioi.NUiiRci. Cardinal Spline Interpolation \\.\\ SiMii.R. The Theory of Best Approximation and Functional Analysis WI-.KNI R C. RHHINBOLDT, Methods of Solving Systems of Nonlinear Equations HANS I-'. WHINBKRQKR, Variational Methods for Eigenvalue Approximation R. TYRRM.I. ROCKAI-KLI.AK, Conjugate Dtialitv and Optimization SIR JAMKS LIGHTHILL, Mathematical Biofhtiddynamics GI-.RAKD SAI.ION, Theory of Indexing C \ rnLi-:i;.N S. MORAWKTX, Notes on Time Decay and Scattering for Some Hyperbolic Problems F. Hoi'i'hNSTKAm, Mathematical Theories of Populations: Demographics, Genetics and Epidemics RK HARD ASKF;Y. Orthogonal Polynomials and Special Functions L. H. PAYNI:. Improperly Posed Problems in Partial Differential Equations S. ROSI:N, lectures on the Measurement and Evaluation of the Performance of Computing Systems HHRBHRT B. KI;I.I.I:R. Numerical Solution of Two Point Boundary Value Problems }. P. L.ASxLi.i., The Stability of Dynamical Systems - Z. ARTSTKIN, Appendix A: Limiting Equations and Stability of Nonautonomous Ordinary Differential Equations I), (ion in B AND S. A. ORS/AC,, Numerical Analysis of Spectral Methods: Theon and Applications Pi ii R .1. H I B I - R. Robust Statistical Procedures Hi RBI K r SOLOMON, Geometric Probability FRI:D S. ROBF.RIS, Graph Theory and Its Applications to Problems of Society .Ii RIS H A R I M - \ N I S. Feasible Computations and Provable Complexity Properties ZOIIAR MANNA, Lectures on the Logic of Computer Programming F.I I is L. JOHNSON, Integer Programming: Facets, Subadditivitv, and Duality for Group and Semi- Group Problems S H N H I -I WINOGRAD, Arithmetic Complexity of Computations J. F. C. KiNCiMAN. Mathematics of Genetic Diversity M O R I ON F. GiuiTiN. Topics in Finite Elasticity TIIOMXS G. K t i R f X, Approximation of Population Processes (continued on inside back coven

Robert Endre Tarjan Bell Laboratories Murray Hill, New Jersey Data Structures and Network Algorithms Siam. SOCIETY FOR INDUSTRIAL AND APPLIED MATHEMATICS PHILADELPHIA

Copyright ©1983 by the Society for Industrial and Applied Mathematics. 109 All rights reserved. Printed in the United States of America. No part of this book may be reproduced, stored, or transmitted in any manner without the written permission of the publisher. For information, write to the Society for Industrial and Applied Mathematics, 3600 University City Science Center, Philadelphia, PA 19104-2688. Library of Congress Catalog Card Number: 83-61374 ISBN 0-89871-187-8 • Siamumm is a is a is a registered trademark.

To Gail Maria Zawacki

This page intentionally left blank

Contents Preface Chapter 1 FOUNDATIONS 1.1. Introduction 1.2. Computational complexity 1.3. Primitive data structures 1.4. Algorithmic notation 1.5. Trees and graphs Chapter 2 DISJOINT SETS 2.1. Disjoint sets and compressed trees 2.2. An amortized upper bound for path compression 2.3. Remarks Chapter 3 HEAPS 3.1. Heaps and heap-ordered trees 3.2. Cheaps 3.3. Leftist heaps 3.4. Remarks Chapter 4 SEARCH TREES 4.1. Sorted sets and binary search trees 4.2. Balanced binary trees 4.3. Self-adjusting binary trees Chapter 5 LINKING AND CUTTING TREES 5.1. The problem of linking and cutting trees 5.2. Representing trees as sets of paths 5.3. Representing paths as binary trees 5.4. Remarks V vii 1 2 7 12 14 23 24 29 33 34 38 42 45 48 53 59 60 64 70

VI CONTENTS Chapter 6 MINIMUM SPANNING TREES 6.1. The greedy method 6.2. Three classical algorithms 6.3. The round robin algorithm 6.4. Remarks Chapter 7 SHORTEST PATHS 7.1. Shortest-path trees and labeling and scanning 7.2. Efficient scanning orders 7.3. All pairs Chapter 8 NETWORK FLOWS 8.1. Flows, cuts, and augmenting paths 8.2. Augmenting by blocking flows 8.3. Finding blocking flows 8.4. Minimum cost flows Chapter 9 MATCHINGS 9.1. Bipartite matchings and network flows 9.2. Alternating paths 9.3. Blossoms 9.4. Algorithms for nonbipartite matching References 71 72 77 81 85 89 94 97 102 104 108 113 114 115 119 125

分享到：

赞收藏

资料库

Data Structures and Network Algorithms.pdf

相关推荐

课程资源

热门标签

最新资料