DOI: 10.1007/3-540-59408-6_49. On implementing push-relabel method for the maximum flow problem

On implementing push-relabel method for the maximum flow problem

10.1007/3-540-59408-6_49

Crossref book-chapter

Springer Berlin Heidelberg

Lecture Notes in Computer Science (297)

Bibliography

Cherkassky, B. V., & Goldberg, A. V. (1995). On implementing push-relabel method for the maximum flow problem. Integer Programming and Combinatorial Optimization, 157â171.

Authors 2

Boris V. Cherkassky (first)
Andrew V. Goldberg (additional)

References 23 Referenced 40

R. K. Ahuja, J. B. Orlin, and R. E. Tarjan. Improved Time Bounds for the Maximum Flow Problem. SIAM J. Comput., 18:939–954, 1989. (10.1137/0218065) / SIAM J. Comput. by R. K. Ahuja (1989)
R. J. Anderson and J. C. Setubal. Goldberg's Algorithm for the Maximum Flow in Perspective: a Computational Study. In D. S. Johnson and C. C. McGeoch, editors, Network Flows and Matching: First DIMACS Implementation Challenge, pages 1–18. AMS, 1993. (10.1090/dimacs/012/01)
J. Cheriyan, T. Hagerup, and K. Mehlhorn. Can a Maximum Flow be Computed in o(nm) Time? In Proc. ICALP, 1990. (10.1007/BFb0032035)
J. Cheriyan and S. N. Maheshwari. Analysis of Preflow Push Algorithms for Maximum Netwrok Flow. SIAM J. Comput., 18:1057–1086, 1989. (10.1137/0218072) / SIAM J. Comput. by J. Cheriyan (1989)
B. V. Cherkassky. A Fast Algorithm for Computing Maximum Flow in a Network. In A. V. Karzanov, editor, Collected Papers, Issue 3: Combinatorial Methods for Flow Problems, pages 90–96. The Institute for Systems Studies, Moscow, 1979. In Russian. English translation appears in AMS Trans., Vol. 158, pp. 23–30, 1994. / Collected Papers, Issue 3: Combinatorial Methods for Flow Problems by B. V. Cherkassky (1979)
G. B. Dantzig. Application of the Simplex Method to a Transportation Problem. In T. C. Koopmans, editor, Activity Analysis and Production and Allocation, pages 359–373. Wiley, New York, 1951. / Activity Analysis and Production and Allocation by G. B. Dantzig (1951)
G. B. Dantzig. Linear Programming and Extensions. Princeton Univ. Press, Princeton, NJ, 1962. / Linear Programming and Extensions by G. B. Dantzig (1962)
U. Derigs and W. Meier. Implementing Goldberg's Max-Flow Algorithm — A Computational Investigation. ZOR — Methods and Models of Operations Research, 33:383–403, 1989. (10.1007/BF01415937) / ZOR — Methods and Models of Operations Research by U. Derigs (1989)
U. Derigs and W. Meier. An Evaluation of Algorithmic Refinements and Proper Data-Structures for the Preflow-Push Approach for Maximum Flow. In ASI Series on Computer and System Sciences, volume 8, pages 209–223. NATO, 1992. (10.1007/978-3-642-77489-8_3)
E. A. Dinic. Algorithm for Solution of a Problem of Maximum Flow in Networks with Power Estimation. Soviet Math. Dokl., 11:1277–1280, 1970. / Soviet Math. Dokl. by E. A. Dinic (1970)
J. Edmonds and R. M. Karp. Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems. J. Assoc. Comput. Mach., 19:248–264, 1972. (10.1145/321694.321699) / J. Assoc. Comput. Mach. by J. Edmonds (1972)
L. R. Ford, Jr. and D. R. Fulkerson. Flows in Networks. Princeton Univ. Press, Princeton, NJ, 1962. / Flows in Networks by L. R. Ford Jr. (1962)
A. V. Goldberg. A New Max-Flow Algorithm. Technical Report MIT/LCS/TM-291, Laboratory for Computer Science, M.I.T., 1985.
A. V. Goldberg. Efficient Graph Algorithms for Sequential and Parallel Computers. PhD thesis, M.I.T., January 1987. (Also available as Technical Report TR-374, Lab. for Computer Science, M.I.T., 1987).
A. V. Goldberg, É. Tardos, and R. E. Tarjan. Network Flow Algorithms. In B. Korte, L. Lovász, H. J. Prömel, and A. Schrijver, editors, Flows, Paths, and VLSI Layout, pages 101–164. Springer Verlag, 1990. (10.21236/ADA214689)
A. V. Goldberg and R. E. Tarjan. A New Approach to the Maximum Flow Problem. In Proc. 18th Annual ACM Symposium on Theory of Computing, pages 136–146, 1986. (10.1145/12130.12144)
A. V. Goldberg and R. E. Tarjan. A New Approach to the Maximum Flow Problem. J. Assoc. Comput. Mach., 35:921–940, 1988. (10.1145/48014.61051) / J. Assoc. Comput. Mach. by A. V. Goldberg (1988)
D. Goldfarb and M. D. Grigoriadis. A Computational Comparison of the Dinic and Network Simplex Methods for Maximum Flow. Annals of Oper. Res., 13:83–123, 1988. (10.1007/BF02288321) / Annals of Oper. Res. by D. Goldfarb (1988)
D. S. Johnson and C. C. McGeoch, editors. Network Flows and Matching: First DIMACS Implementation Challenge. AMS, 1993. (10.1090/dimacs/012)
A. V. Karzanov. Determining the Maximal Flow in a Network by the Method of Preflows. Soviet Math. Dok., 15:434–437, 1974. / Soviet Math. Dok. by A. V. Karzanov (1974)
V. King, S. Rao, and R. Tarjan. A Faster Deterministic Maximum Flow Algorithm. In Proc. 3rd ACM-SIAM Symposium on Discrete Algorithms, pages 157–164, 1992.
Q. C. Nguyen and V. Venkateswaran. Implementations of Goldberg-Tarjan Maximum Flow Algorithm. In D. S. Johnson and C. C. McGeoch, editors, Network Flows and Matching: First DIMACS Implementation Challenge, pages 19–42. AMS, 1993. (10.1090/dimacs/012/02)
R. E. Tarjan. A Simple Version of Karzanov's Blocking Flow Algorithm. Operations Research Letters, 2:265–268, 1984. (10.1016/0167-6377(84)90076-2) / Operations Research Letters by R. E. Tarjan (1984)

Dates

Type	When
Created	13 years, 6 months ago (Feb. 26, 2012, 12:15 p.m.)
Deposited	4 years, 9 months ago (Nov. 17, 2020, 4:27 p.m.)
Indexed	3 months, 2 weeks ago (May 18, 2025, 2:06 a.m.)
Issued	30 years, 8 months ago (Jan. 1, 1995)
Published	30 years, 8 months ago (Jan. 1, 1995)
Published Online	20 years, 3 months ago (June 1, 2005)
Published Print	30 years, 8 months ago (Jan. 1, 1995)

Funders 0

None

BibTeX

@inbook{Cherkassky_1995, title={On implementing push-relabel method for the maximum flow problem}, ISBN={9783540492450}, ISSN={1611-3349}, url={http://dx.doi.org/10.1007/3-540-59408-6_49}, DOI={10.1007/3-540-59408-6_49}, booktitle={Integer Programming and Combinatorial Optimization}, publisher={Springer Berlin Heidelberg}, author={Cherkassky, Boris V. and Goldberg, Andrew V.}, year={1995}, pages={157–171} }

JSON

{
  "indexed": {
    "date-parts": [
      [
        2025,
        5,
        18
      ]
    ],
    "date-time": "2025-05-18T06:06:14Z",
    "timestamp": 1747548374088
  },
  "publisher-location": "Berlin, Heidelberg",
  "reference-count": 23,
  "publisher": "Springer Berlin Heidelberg",
  "isbn-type": [
    {
      "type": "print",
      "value": "9783540594086"
    },
    {
      "type": "electronic",
      "value": "9783540492450"
    }
  ],
  "content-domain": {
    "domain": [],
    "crossmark-restriction": false
  },
  "published-print": {
    "date-parts": [
      [
        1995
      ]
    ]
  },
  "DOI": "10.1007/3-540-59408-6_49",
  "type": "book-chapter",
  "created": {
    "date-parts": [
      [
        2012,
        2,
        26
      ]
    ],
    "date-time": "2012-02-26T17:15:17Z",
    "timestamp": 1330276517000
  },
  "page": "157-171",
  "source": "Crossref",
  "is-referenced-by-count": 40,
  "title": "On implementing push-relabel method for the maximum flow problem",
  "prefix": "10.1007",
  "author": [
    {
      "given": "Boris V.",
      "family": "Cherkassky",
      "sequence": "first",
      "affiliation": []
    },
    {
      "given": "Andrew V.",
      "family": "Goldberg",
      "sequence": "additional",
      "affiliation": []
    }
  ],
  "member": "297",
  "published-online": {
    "date-parts": [
      [
        2005,
        6,
        1
      ]
    ]
  },
  "reference": [
    {
      "key": "13_CR1",
      "doi-asserted-by": "crossref",
      "first-page": "939",
      "DOI": "10.1137/0218065",
      "volume": "18",
      "author": "R. K. Ahuja",
      "year": "1989",
      "unstructured": "R. K. Ahuja, J. B. Orlin, and R. E. Tarjan. Improved Time Bounds for the Maximum Flow Problem. SIAM J. Comput., 18:939\u2013954, 1989.",
      "journal-title": "SIAM J. Comput."
    },
    {
      "key": "13_CR2",
      "doi-asserted-by": "crossref",
      "unstructured": "R. J. Anderson and J. C. Setubal. Goldberg's Algorithm for the Maximum Flow in Perspective: a Computational Study. In D. S. Johnson and C. C. McGeoch, editors, Network Flows and Matching: First DIMACS Implementation Challenge, pages 1\u201318. AMS, 1993.",
      "DOI": "10.1090/dimacs/012/01"
    },
    {
      "key": "13_CR3",
      "doi-asserted-by": "crossref",
      "unstructured": "J. Cheriyan, T. Hagerup, and K. Mehlhorn. Can a Maximum Flow be Computed in o(nm) Time? In Proc. ICALP, 1990.",
      "DOI": "10.1007/BFb0032035"
    },
    {
      "key": "13_CR4",
      "doi-asserted-by": "crossref",
      "first-page": "1057",
      "DOI": "10.1137/0218072",
      "volume": "18",
      "author": "J. Cheriyan",
      "year": "1989",
      "unstructured": "J. Cheriyan and S. N. Maheshwari. Analysis of Preflow Push Algorithms for Maximum Netwrok Flow. SIAM J. Comput., 18:1057\u20131086, 1989.",
      "journal-title": "SIAM J. Comput."
    },
    {
      "key": "13_CR5",
      "first-page": "90",
      "volume-title": "Collected Papers, Issue 3: Combinatorial Methods for Flow Problems",
      "author": "B. V. Cherkassky",
      "year": "1979",
      "unstructured": "B. V. Cherkassky. A Fast Algorithm for Computing Maximum Flow in a Network. In A. V. Karzanov, editor, Collected Papers, Issue 3: Combinatorial Methods for Flow Problems, pages 90\u201396. The Institute for Systems Studies, Moscow, 1979. In Russian. English translation appears in AMS Trans., Vol. 158, pp. 23\u201330, 1994."
    },
    {
      "key": "13_CR6",
      "first-page": "359",
      "volume-title": "Activity Analysis and Production and Allocation",
      "author": "G. B. Dantzig",
      "year": "1951",
      "unstructured": "G. B. Dantzig. Application of the Simplex Method to a Transportation Problem. In T. C. Koopmans, editor, Activity Analysis and Production and Allocation, pages 359\u2013373. Wiley, New York, 1951."
    },
    {
      "key": "13_CR7",
      "volume-title": "Linear Programming and Extensions",
      "author": "G. B. Dantzig",
      "year": "1962",
      "unstructured": "G. B. Dantzig. Linear Programming and Extensions. Princeton Univ. Press, Princeton, NJ, 1962."
    },
    {
      "key": "13_CR8",
      "doi-asserted-by": "crossref",
      "first-page": "383",
      "DOI": "10.1007/BF01415937",
      "volume": "33",
      "author": "U. Derigs",
      "year": "1989",
      "unstructured": "U. Derigs and W. Meier. Implementing Goldberg's Max-Flow Algorithm \u2014 A Computational Investigation. ZOR \u2014 Methods and Models of Operations Research, 33:383\u2013403, 1989.",
      "journal-title": "ZOR \u2014 Methods and Models of Operations Research"
    },
    {
      "key": "13_CR9",
      "doi-asserted-by": "crossref",
      "unstructured": "U. Derigs and W. Meier. An Evaluation of Algorithmic Refinements and Proper Data-Structures for the Preflow-Push Approach for Maximum Flow. In ASI Series on Computer and System Sciences, volume 8, pages 209\u2013223. NATO, 1992.",
      "DOI": "10.1007/978-3-642-77489-8_3"
    },
    {
      "key": "13_CR10",
      "first-page": "1277",
      "volume": "11",
      "author": "E. A. Dinic",
      "year": "1970",
      "unstructured": "E. A. Dinic. Algorithm for Solution of a Problem of Maximum Flow in Networks with Power Estimation. Soviet Math. Dokl., 11:1277\u20131280, 1970.",
      "journal-title": "Soviet Math. Dokl."
    },
    {
      "key": "13_CR11",
      "doi-asserted-by": "crossref",
      "first-page": "248",
      "DOI": "10.1145/321694.321699",
      "volume": "19",
      "author": "J. Edmonds",
      "year": "1972",
      "unstructured": "J. Edmonds and R. M. Karp. Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems. J. Assoc. Comput. Mach., 19:248\u2013264, 1972.",
      "journal-title": "J. Assoc. Comput. Mach."
    },
    {
      "key": "13_CR12",
      "volume-title": "Flows in Networks",
      "author": "L. R. Ford Jr.",
      "year": "1962",
      "unstructured": "L. R. Ford, Jr. and D. R. Fulkerson. Flows in Networks. Princeton Univ. Press, Princeton, NJ, 1962."
    },
    {
      "key": "13_CR13",
      "unstructured": "A. V. Goldberg. A New Max-Flow Algorithm. Technical Report MIT/LCS/TM-291, Laboratory for Computer Science, M.I.T., 1985."
    },
    {
      "key": "13_CR14",
      "unstructured": "A. V. Goldberg. Efficient Graph Algorithms for Sequential and Parallel Computers. PhD thesis, M.I.T., January 1987. (Also available as Technical Report TR-374, Lab. for Computer Science, M.I.T., 1987)."
    },
    {
      "key": "13_CR15",
      "doi-asserted-by": "crossref",
      "unstructured": "A. V. Goldberg, \u00c9. Tardos, and R. E. Tarjan. Network Flow Algorithms. In B. Korte, L. Lov\u00e1sz, H. J. Pr\u00f6mel, and A. Schrijver, editors, Flows, Paths, and VLSI Layout, pages 101\u2013164. Springer Verlag, 1990.",
      "DOI": "10.21236/ADA214689"
    },
    {
      "key": "13_CR16",
      "doi-asserted-by": "crossref",
      "unstructured": "A. V. Goldberg and R. E. Tarjan. A New Approach to the Maximum Flow Problem. In Proc. 18th Annual ACM Symposium on Theory of Computing, pages 136\u2013146, 1986.",
      "DOI": "10.1145/12130.12144"
    },
    {
      "key": "13_CR17",
      "doi-asserted-by": "crossref",
      "first-page": "921",
      "DOI": "10.1145/48014.61051",
      "volume": "35",
      "author": "A. V. Goldberg",
      "year": "1988",
      "unstructured": "A. V. Goldberg and R. E. Tarjan. A New Approach to the Maximum Flow Problem. J. Assoc. Comput. Mach., 35:921\u2013940, 1988.",
      "journal-title": "J. Assoc. Comput. Mach."
    },
    {
      "key": "13_CR18",
      "doi-asserted-by": "crossref",
      "first-page": "83",
      "DOI": "10.1007/BF02288321",
      "volume": "13",
      "author": "D. Goldfarb",
      "year": "1988",
      "unstructured": "D. Goldfarb and M. D. Grigoriadis. A Computational Comparison of the Dinic and Network Simplex Methods for Maximum Flow. Annals of Oper. Res., 13:83\u2013123, 1988.",
      "journal-title": "Annals of Oper. Res."
    },
    {
      "key": "13_CR19",
      "doi-asserted-by": "crossref",
      "unstructured": "D. S. Johnson and C. C. McGeoch, editors. Network Flows and Matching: First DIMACS Implementation Challenge. AMS, 1993.",
      "DOI": "10.1090/dimacs/012"
    },
    {
      "key": "13_CR20",
      "first-page": "434",
      "volume": "15",
      "author": "A. V. Karzanov",
      "year": "1974",
      "unstructured": "A. V. Karzanov. Determining the Maximal Flow in a Network by the Method of Preflows. Soviet Math. Dok., 15:434\u2013437, 1974.",
      "journal-title": "Soviet Math. Dok."
    },
    {
      "key": "13_CR21",
      "unstructured": "V. King, S. Rao, and R. Tarjan. A Faster Deterministic Maximum Flow Algorithm. In Proc. 3rd ACM-SIAM Symposium on Discrete Algorithms, pages 157\u2013164, 1992."
    },
    {
      "key": "13_CR22",
      "doi-asserted-by": "crossref",
      "unstructured": "Q. C. Nguyen and V. Venkateswaran. Implementations of Goldberg-Tarjan Maximum Flow Algorithm. In D. S. Johnson and C. C. McGeoch, editors, Network Flows and Matching: First DIMACS Implementation Challenge, pages 19\u201342. AMS, 1993.",
      "DOI": "10.1090/dimacs/012/02"
    },
    {
      "key": "13_CR23",
      "doi-asserted-by": "crossref",
      "first-page": "265",
      "DOI": "10.1016/0167-6377(84)90076-2",
      "volume": "2",
      "author": "R. E. Tarjan",
      "year": "1984",
      "unstructured": "R. E. Tarjan. A Simple Version of Karzanov's Blocking Flow Algorithm. Operations Research Letters, 2:265\u2013268, 1984.",
      "journal-title": "Operations Research Letters"
    }
  ],
  "container-title": "Lecture Notes in Computer Science",
  "original-title": [],
  "link": [
    {
      "URL": "http://link.springer.com/content/pdf/10.1007/3-540-59408-6_49.pdf",
      "content-type": "unspecified",
      "content-version": "vor",
      "intended-application": "similarity-checking"
    }
  ],
  "deposited": {
    "date-parts": [
      [
        2020,
        11,
        17
      ]
    ],
    "date-time": "2020-11-17T21:27:02Z",
    "timestamp": 1605648422000
  },
  "score": 1,
  "resource": {
    "primary": {
      "URL": "http://link.springer.com/10.1007/3-540-59408-6_49"
    }
  },
  "subtitle": [],
  "short-title": [],
  "issued": {
    "date-parts": [
      [
        1995
      ]
    ]
  },
  "ISBN": [
    "9783540594086",
    "9783540492450"
  ],
  "references-count": 23,
  "URL": "http://dx.doi.org/10.1007/3-540-59408-6_49",
  "relation": {},
  "ISSN": [
    "0302-9743",
    "1611-3349"
  ],
  "subject": [],
  "published": {
    "date-parts": [
      [
        1995
      ]
    ]
  }
}