The DOI matches its Crossref record.
Network Flows: Theory, Algorithms, and Applications.
Abstract
A comprehensive introduction to network flows that brings together the classic and the contemporary aspects of the field, and provides an integrative view of theory, algorithms, and applications. presents in-depth, self-contained treatments of shortest path, maximum flow, and minimum cost flow problems, including descriptions of polynomial-time algorithms for these core models. emphasizes powerful algorithmic strategies and analysis tools such as data scaling, geometric improvement arguments, and potential function arguments. provides an easy-to-understand descriptions of several important data structures, including d-heaps, Fibonacci heaps, and dynamic trees. devotes a special chapter to conducting empirical testing of algorithms. features over 150 applications of network flows to a variety of engineering, management, and scientific domains. contains extensive reference notes and illustrations.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cited by
The Structure and Function of Complex Networks
Newman, M. E. J. (2003) · SIAM Review · doi:10.1137/s003614450342480 · Cited by 18,719
Community structure in social and biological networks
Girvan, M., & Newman, M. E. J. (2002) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.122653799 · Cited by 15,502
Finding and evaluating community structure in networks
Newman, M. E. J., & Girvan, M. (2004) · Physical Review E · doi:10.1103/physreve.69.026113 · Cited by 13,931
Fortunato, S. (2010) · Physics Reports · doi:10.1016/j.physrep.2009.11.002 · Cited by 11,293
Complex networks: structure and dynamics
BOCCALETTI, S., LATORA, V, MORENO, Y., CHAVEZ, M., & HWANG, D. (2006) · Physics Reports · doi:10.1016/j.physrep.2005.10.009 · Cited by 11,010
Fast approximate energy minimization via graph cuts
Boykov, Y., Veksler, O., & Zabih, R. (2001) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/34.969114 · Cited by 6,988
t-Closeness: Privacy Beyond k-Anonymity and l-Diversity
Li, N., Li, T., & Venkatasubramanian, S. (2007) · 2007 IEEE 23rd International Conference on Data Engineering · doi:10.1109/icde.2007.367856 · Cited by 3,451
A sentimental education: sentiment analysis using subjectivity summarization based on minimum cuts
Pang, B., & Lee, L. (2004) · Proceedings of the 42nd Annual Meeting on Association for Computational Linguistics - ACL '04 · doi:10.3115/1218955.1218990 · Cited by 3,301
What energy functions can be minimized via graph cuts?
Kolmogorov, V., & Zabih, R. (2004) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2004.1262177 · Cited by 3,127
Network-based statistic: identifying differences in brain networks
Zalesky, A., Fornito, A., & Bullmore, E. T. (2010) · NeuroImage · doi:10.1016/j.neuroimage.2010.06.041 · Cited by 2,750
Scientific collaboration networks. II. Shortest paths, weighted networks, and centrality
Newman, M. E. J. (2001) · Physical Review E · doi:10.1103/physreve.64.016132 · Cited by 2,613
Newman, M. E. J. (2004) · Physical Review E · doi:10.1103/physreve.70.056131 · Cited by 2,476
A measure of betweenness centrality based on random walks
Newman, M. E. J. (2005) · Social Networks · doi:10.1016/j.socnet.2004.11.009 · Cited by 2,461
Lehner, B., & Grill, G. (2013) · Hydrological Processes · doi:10.1002/hyp.9740 · Cited by 2,193
Detecting community structure in networks
Newman, M. E. J. (2004) · The European Physical Journal B - Condensed Matter · doi:10.1140/epjb/e2004-00124-y · Cited by 2,028
Coauthorship networks and patterns of scientific collaboration
Newman, M. E. J. (2004) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.0307545100 · Cited by 1,931
Robust discrete optimization and network flows
Bertsimas, D., & Sim, M. (2003) · Mathematical Programming · doi:10.1007/s10107-003-0396-4 · Cited by 1,799
A Formal Analysis and Taxonomy of Task Allocation in Multi-Robot Systems
Gerkey, B. P., & Matarić, M. J. (2004) · The International Journal of Robotics Research · doi:10.1177/0278364904045564 · Cited by 1,753
Railroads of the Raj: Estimating the Impact of Transportation Infrastructure
Donaldson, D. (2018) · American Economic Review · doi:10.1257/aer.20101199 · Cited by 1,634
Rethinking virtual network embedding: substrate support for path splitting and migration
Yu, M., Yi, Y., Rexford, J., & Chiang, M. (2008) · ACM SIGCOMM Computer Communication Review · doi:10.1145/1355734.1355737 · Cited by 1,244
Railroads and American Economic Growth: A “Market Access” Approach *
Donaldson, D., & Hornbeck, R. (2016) · The Quarterly Journal of Economics · doi:10.1093/qje/qjw002 · Cited by 1,238
Watts, D. J. (2004) · Annual Review of Sociology · doi:10.1146/annurev.soc.30.020404.104342 · Cited by 1,163
Computing visual correspondence with occlusions using graph cuts
Kolmogorov, V., & Zabih, R. (2002) · Proceedings Eighth IEEE International Conference on Computer Vision. ICCV 2001 · doi:10.1109/iccv.2001.937668 · Cited by 1,119
Integer and combinatorial optimization
(1999) · Computers & Mathematics with Applications · doi:10.1016/s0898-1221(99)91259-2 · Cited by 1,117
Self-organization and identification of Web communities
Flake, G. W., Lawrence, S., Giles, C. L., & Coetzee, F. M. (2002) · Computer · doi:10.1109/2.989932 · Cited by 1,018
Optimal Transport for Domain Adaptation
Courty, N., Flamary, R., Tuia, D., & Rakotomamonjy, A. (2017) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2016.2615921 · Cited by 989
Bonet, B., & Geffner, H. (2001) · Artificial Intelligence · doi:10.1016/s0004-3702(01)00108-4 · Cited by 959
Global data association for multi-object tracking using network flows
Zhang, L., Li, Y., & Nevatia, R. (2008) · 2008 IEEE Conference on Computer Vision and Pattern Recognition · doi:10.1109/cvpr.2008.4587584 · Cited by 925
Distributed Cooperative Secondary Control of Microgrids Using Feedback Linearization
Bidram, A., Davoudi, A., Lewis, F. L., & Guerrero, J. M. (2013) · IEEE Transactions on Power Systems · doi:10.1109/tpwrs.2013.2247071 · Cited by 924
The Cross-Entropy Method for Combinatorial and Continuous Optimization
Rubinstein, R. (1999) · Methodology And Computing In Applied Probability · doi:10.1023/a:1010091220143 · Cited by 903
A Framework for Generating Network-Based Moving Objects
Brinkhoff, T. (2002) · GeoInformatica · doi:10.1023/a:1015231126594 · Cited by 862
Pre-positioning of emergency supplies for disaster response
Rawls, C. G., & Turnquist, M. A. (2010) · Transportation Research Part B: Methodological · doi:10.1016/j.trb.2009.08.003 · Cited by 856
Chen, C. W., & Zebker, H. A. (2002) · IEEE Transactions on Geoscience and Remote Sensing · doi:10.1109/tgrs.2002.802453 · Cited by 843
Measurement and correction of systematic odometry errors in mobile robots
Borenstein, J., & Feng, L. (1996) · IEEE Transactions on Robotics and Automation · doi:10.1109/70.544770 · Cited by 807
Fast and robust Earth Mover's Distances
Pele, O., & Werman, M. (2009) · 2009 IEEE 12th International Conference on Computer Vision · doi:10.1109/iccv.2009.5459199 · Cited by 805
Efficient identification of Web communities
Flake, G. W., Lawrence, S., & Giles, C. L. (2000) · Proceedings of the sixth ACM SIGKDD international conference on Knowledge discovery and data mining · doi:10.1145/347090.347121 · Cited by 804
Transcriptome genetics using second generation sequencing in a Caucasian population
Montgomery, S. B., Sammeth, M., Gutierrez-Arcelus, M., Lach, R. P., Ingle, C., Nisbett, J., Guigo, R., & Dermitzakis, E. T. (2010) · Nature · doi:10.1038/nature08903 · Cited by 797
Globally-optimal greedy algorithms for tracking a variable number of objects
Pirsiavash, H., Ramanan, D., & Fowlkes, C. C. (2011) · CVPR 2011 · doi:10.1109/cvpr.2011.5995604 · Cited by 790
Smart “Predict, then Optimize”
Elmachtoub, A. N., & Grigas, P. (2022) · Management Science · doi:10.1287/mnsc.2020.3922 · Cited by 773
A Microscopic Traffic Simulator for evaluation of dynamic traffic management systems
Yang, Q., & Koutsopoulos, H. N. (1996) · Transportation Research Part C: Emerging Technologies · doi:10.1016/s0968-090x(96)00006-x · Cited by 746
Multi-camera Scene Reconstruction via Graph Cuts
Kolmogorov, V., & Zabih, R. (2002) · Lecture Notes in Computer Science · doi:10.1007/3-540-47977-5_6 · Cited by 739
Optimal Full Matching and Related Designs via Network Flows
Hansen, B. B., & Klopfer, S. O. (2006) · Journal of Computational and Graphical Statistics · doi:10.1198/106186006x137047 · Cited by 703
A Sentimental Education: Sentiment Analysis Using Subjectivity Summarization Based on Minimum Cuts
Pang, B., & Lee, L. (2004) · arXiv (Cornell University) · doi:10.48550/arxiv.cs/0409058 · Cited by 652
Selfish Routing and the Price of Anarchy
(2016) · Twenty Lectures on Algorithmic Game Theory · doi:10.1017/cbo9781316779309.012 · Cited by 647
Multi-animal pose estimation, identification and tracking with DeepLabCut
Lauer, J., Zhou, M., Ye, S., Menegas, W., Schneider, S., Nath, T., Rahman, M. M., Di Santo, V., Soberanes, D., Feng, G., et al. (2022) · Nature Methods · doi:10.1038/s41592-022-01443-0 · Cited by 647
The image foresting transform: theory, algorithms, and applications
Falcao, A. X., Stolfi, J., & de Alencar Lotufo, R. (2004) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2004.1261076 · Cited by 614
Shortest Path Problems with Resource Constraints
Irnich, S., & Desaulniers, G. (2006) · Column Generation · doi:10.1007/0-387-25486-2_2 · Cited by 597
Managing and Mining Graph Data
(2010) · Advances in Database Systems · doi:10.1007/978-1-4419-6045-0 · Cited by 594
Social Media Mining: An Introduction
Zafarani, R., Abbasi, M. A., & Liu, H. (2014) · Cambridge University Press eBooks · doi:10.1017/cbo9781139088510 · Cited by 592
Planning models for freight transportation
Crainic, T. G., & Laporte, G. (1997) · European Journal of Operational Research · doi:10.1016/s0377-2217(96)00298-6 · Cited by 592
Railroads of the Raj: Estimating the Impact of Transportation Infrastructure
Donaldson, D. (2010) · National Bureau of Economic Research · doi:10.3386/w16487 · Cited by 579
Capacity reliability of a road network: an assessment methodology and numerical results
Chen, A., Yang, H., Lo, H. K., & Tang, W. H. (2002) · Transportation Research Part B: Methodological · doi:10.1016/s0191-2615(00)00048-5 · Cited by 565
An introduction to continuous optimization for imaging
Chambolle, A., & Pock, T. (2016) · Acta Numerica · doi:10.1017/s096249291600009x · Cited by 545
Virtual network embedding through topology-aware node ranking
Cheng, X., Su, S., Zhang, Z., Wang, H., Yang, F., Luo, Y., & Wang, J. (2011) · ACM SIGCOMM Computer Communication Review · doi:10.1145/1971162.1971168 · Cited by 544
Secondary control of microgrids based on distributed cooperative control of multi‐agent systems
Bidram, A., Davoudi, A., Lewis, F. L., & Qu, Z. (2013) · IET Generation, Transmission & Distribution · doi:10.1049/iet-gtd.2012.0576 · Cited by 541
Resnik, P., & Smith, N. A. (2003) · Computational Linguistics · doi:10.1162/089120103322711578 · Cited by 522
Learning a Neural Solver for Multiple Object Tracking
Braso, G., & Leal-Taixe, L. (2020) · 2020 IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR) · doi:10.1109/cvpr42600.2020.00628 · Cited by 504
A network flow model for lane-based evacuation routing
Cova, T. J., & Johnson, J. P. (2003) · Transportation Research Part A: Policy and Practice · doi:10.1016/s0965-8564(03)00007-7 · Cited by 475
A Survey on PageRank Computing
Berkhin, P. (2005) · Internet Mathematics · doi:10.1080/15427951.2005.10129098 · Cited by 474
Fast approximate energy minimization via graph cuts
Boykov, Y., Veksler, O., & Zabih, R. (1999) · Proceedings of the Seventh IEEE International Conference on Computer Vision · doi:10.1109/iccv.1999.791245 · Cited by 470
Designing and reporting on computational experiments with heuristic methods
Barr, R. S., Golden, B. L., Kelly, J. P., Resende, M. G. C., & Stewart, W. R. (1995) · Journal of Heuristics · doi:10.1007/bf02430363 · Cited by 448
A two-level network for recycling sand: A case study
Barros, A. I., Dekker, R., & Scholten, V. (1998) · European Journal of Operational Research · doi:10.1016/s0377-2217(98)00093-9 · Cited by 447
Scientific collaboration and endorsement: Network analysis of coauthorship and citation networks
Ding, Y. (2011) · Journal of Informetrics · doi:10.1016/j.joi.2010.10.008 · Cited by 438
Geometric Shortest Paths and Network Optimization
Mitchell, J. S. B. (2000) · Handbook of Computational Geometry · doi:10.1016/b978-044482537-7/50016-4 · Cited by 427
Optimizing Binary MRFs via Extended Roof Duality
Rother, C., Kolmogorov, V., Lempitsky, V., & Szummer, M. (2007) · 2007 IEEE Conference on Computer Vision and Pattern Recognition · doi:10.1109/cvpr.2007.383203 · Cited by 427
Lei, S., Chen, C., Li, Y., & Hou, Y. (2019) · IEEE Transactions on Smart Grid · doi:10.1109/tsg.2019.2899353 · Cited by 427
The fragment assembly string graph
Myers, E. W. (2005) · Bioinformatics · doi:10.1093/bioinformatics/bti1114 · Cited by 424
Blossom V: a new implementation of a minimum cost perfect matching algorithm
Kolmogorov, V. (2009) · Mathematical Programming Computation · doi:10.1007/s12532-009-0002-8 · Cited by 414
Gai, Y., Krishnamachari, B., & Jain, R. (2012) · IEEE/ACM Transactions on Networking · doi:10.1109/tnet.2011.2181864 · Cited by 413
Multi-constrained optimal path selection
Korkmaz, T., & Krunz, M. (2002) · Proceedings IEEE INFOCOM 2001. Conference on Computer Communications. Twentieth Annual Joint Conference of the IEEE Computer and Communications Society (Cat. No.01CH37213) · doi:10.1109/infcom.2001.916274 · Cited by 399
Feature Correspondence Via Graph Matching: Models and Global Optimization
Torresani, L., Kolmogorov, V., & Rother, C. (2008) · Lecture Notes in Computer Science · doi:10.1007/978-3-540-88688-4_44 · Cited by 388
Graph cut based image segmentation with connectivity priors
Vicente, S., Kolmogorov, V., & Rother, C. (2008) · 2008 IEEE Conference on Computer Vision and Pattern Recognition · doi:10.1109/cvpr.2008.4587440 · Cited by 385
Detecting critical nodes in sparse graphs
Arulselvan, A., Commander, C. W., Elefteriadou, L., & Pardalos, P. M. (2009) · Computers & Operations Research · doi:10.1016/j.cor.2008.08.016 · Cited by 381
Desrosiers, J., & Lübbecke, M. E. (2006) · Column Generation · doi:10.1007/0-387-25486-2_1 · Cited by 363
Minimizing Nonsubmodular Functions with Graph Cuts-A Review
Kolmogorov, V., & Rother, C. (2007) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2007.1031 · Cited by 362
Social Network Analysis and Mining for Business Applications
Bonchi, F., Castillo, C., Gionis, A., & Jaimes, A. (2011) · ACM Transactions on Intelligent Systems and Technology · doi:10.1145/1961189.1961194 · Cited by 359
Towards enhancing the last-mile delivery: An effective crowd-tasking model with scalable solutions
Wang, Y., Zhang, D., Liu, Q., Shen, F., & Lee, L. H. (2016) · Transportation Research Part E: Logistics and Transportation Review · doi:10.1016/j.tre.2016.06.002 · Cited by 352
Heuristic shortest path algorithms for transportation applications: State of the art
Fu, L., Sun, D., & Rilett, L. R. (2006) · Computers & Operations Research · doi:10.1016/j.cor.2005.03.027 · Cited by 341
Kovács, I. A., Palotai, R., Szalay, M. S., & Csermely, P. (2010) · PLoS ONE · doi:10.1371/journal.pone.0012528 · Cited by 338
Chapter 3 Stochastic and dynamic networks and routing
Powell, W. B., Jaillet, P., & Odoni, A. (1995) · Handbooks in Operations Research and Management Science · doi:10.1016/s0927-0507(05)80107-0 · Cited by 334
Handbook of Mathematical Methods in Imaging
(2011) · Springer eBooks · doi:10.1007/978-0-387-92920-0 · Cited by 334
Optimal Multirobot Path Planning on Graphs: Complete Algorithms and Effective Heuristics
Yu, J., & LaValle, S. M. (2016) · IEEE Transactions on Robotics · doi:10.1109/tro.2016.2593448 · Cited by 331
Effect of long-term cannabis use on axonal fibre connectivity
Zalesky, A., Solowij, N., Yucel, M., Lubman, D. I., Takagi, M., Harding, I. H., Lorenzetti, V., Wang, R., Searle, K., Pantelis, C., et al. (2012) · Brain · doi:10.1093/brain/aws136 · Cited by 326
Using Branch-and-Price-and-Cut to Solve Origin-Destination Integer Multicommodity Flow Problems
Barnhart, C., Hane, C. A., & Vance, P. H. (2000) · Operations Research · doi:10.1287/opre.48.2.318.12378 · Cited by 325
Exact Routing in Large Road Networks Using Contraction Hierarchies
Geisberger, R., Sanders, P., Schultes, D., & Vetter, C. (2012) · Transportation Science · doi:10.1287/trsc.1110.0401 · Cited by 323
A survey of recent developments in multiobjective optimization
Chinchuluun, A., & Pardalos, P. M. (2007) · Annals of Operations Research · doi:10.1007/s10479-007-0186-0 · Cited by 323
A scalable application placement controller for enterprise data centers
Tang, C., Steinder, M., Spreitzer, M., & Pacifici, G. (2007) · Proceedings of the 16th international conference on World Wide Web · doi:10.1145/1242572.1242618 · Cited by 322
Supervised Regionalization Methods: A Survey
Duque, J. C., Ramos, R., & Suriñach, J. (2007) · International Regional Science Review · doi:10.1177/0160017607301605 · Cited by 318
Secure Control Systems: A Quantitative Risk Management Approach
(2015) · IEEE Control Systems · doi:10.1109/mcs.2014.2364709 · Cited by 316
Max flows in O(nm) time, or better
Orlin, J. B. (2013) · Proceedings of the forty-fifth annual ACM symposium on Theory of Computing · doi:10.1145/2488608.2488705 · Cited by 316
Self-citationEvolutionary Network Analysis: A Survey
Aggarwal, C., & Subbian, K. (2014) · ACM Computing Surveys · doi:10.1145/2601412 · Cited by 313
Δ-stepping: a parallelizable shortest path algorithm
Meyer, U., & Sanders, P. (2003) · Journal of Algorithms · doi:10.1016/s0196-6774(03)00076-2 · Cited by 309
Spatial crowdsourcing: a survey
Tong, Y., Zhou, Z., Zeng, Y., Chen, L., & Shahabi, C. (2020) · The VLDB Journal · doi:10.1007/s00778-019-00568-7 · Cited by 305
A compact and efficient image retrieval approach based on border/interior pixel classification
Stehling, R. O., Nascimento, M. A., & Falcão, A. X. (2002) · Proceedings of the eleventh international conference on Information and knowledge management · doi:10.1145/584792.584812 · Cited by 302
Image segmentation with ratio cut
Wang, S., & Siskind, J. M. (2003) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2003.1201819 · Cited by 293
Haffner, S., Pereira, L. F. A., Pereira, L. A., & Barreto, L. S. (2008) · IEEE Transactions on Power Delivery · doi:10.1109/tpwrd.2008.917916 · Cited by 291
Price of Anarchy in Transportation Networks: Efficiency and Optimality Control
Youn, H., Gastner, M. T., & Jeong, H. (2008) · Physical Review Letters · doi:10.1103/physrevlett.101.128701 · Cited by 286
New dynamic programming algorithms for the resource constrained elementary shortest path problem
Righini, G., & Salani, M. (2008) · Networks · doi:10.1002/net.20212 · Cited by 284
COSNET: Connecting Heterogeneous Social Networks with Local and Global Consistency
Zhang, Y., Tang, J., Yang, Z., Pei, J., & Yu, P. S. (2015) · Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining · doi:10.1145/2783258.2783268 · Cited by 283
Kramer, G., Marić, I., & Yates, R. D. (2006) · Foundations and Trends® in Networking · doi:10.1561/1300000004 · Cited by 282
Metadata
- Authors
- Smith, D. K., Ahuja, R. K., Magnanti, T. L., & Orlin, J. B.
- Venue
- The Journal of the Operational Research Society
- Publisher
- JSTOR
- Published
- 1994-11
- Volume
- 45
- Issue
- 11
- Pages
- 1340
- ISSN
- 0160-5682 (ISSN-L)
- OpenAlex
- W1977545325
- Cited by
- 8,034
- References
- 0
- FWCI
- 96.98
- Type
- journal article
- Language
- en
- Open access
- closed
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.