DOI: 10.1006/jagm.1995.0805. An Efficient Implementation of a Scaling Minimum-Cost Flow Algorithm

An Efficient Implementation of a Scaling Minimum-Cost Flow Algorithm

10.1006/jagm.1995.0805

Crossref journal-article

Elsevier BV

Journal of Algorithms (78)

Bibliography

Goldberg, A. V. (1997). An Efficient Implementation of a Scaling Minimum-Cost Flow Algorithm. Journal of Algorithms, 22(1), 1â29.

Authors 1

Andrew V Goldberg (first)

References 36 Referenced 283

10.1016/S0927-0507(89)01005-4 / Optimization. Handbooks in Operations Research and Management Science / Network flows by Ahuja (1989)
{'key': '10.1006/jagm.1995.0805_AL950805RF2', 'series-title': 'Network Flows and Matching: First DIMACS Implementation Challenge', 'first-page': '1', 'article-title': "Goldberg's algorithm for the maximum flow in perspective: A computational study", 'author': 'Anderson', 'year': '1993'} / Network Flows and Matching: First DIMACS Implementation Challenge / Goldberg's algorithm for the maximum flow in perspective: A computational study by Anderson (1993)
D. P. Bertsekas, 1986, Distributed Asynchronous Relaxation Methods for Linear Network Flow Problems, Laboratory for Decision Systems, M.I.T. (10.1109/CDC.1986.267433)
10.1287/opre.36.1.93 / Oper. Res. / Relaxation methods for minimum cost ordinary and generalized network flow problems by Bertsekas (1988)
{'key': '10.1006/jagm.1995.0805_AL950805RF5', 'series-title': 'Network Flows and Matching: First DIMACS Implementation Challenge', 'first-page': '119', 'article-title': 'An empirical study of min cost flow algorithms', 'author': 'Bland', 'year': '1993'} / Network Flows and Matching: First DIMACS Implementation Challenge / An empirical study of min cost flow algorithms by Bland (1993)
10.1007/BF01586039 / Math. Prog. / On the computational behavior of a polynomial-time network flow algorithm by Bland (1992)
10.1287/mnsc.24.1.1 / Management Sci. / Design and implementation of large scale transportation algorithms by Bradley (1977)
10.1145/62038.62041 / ACM Trans. Math. Software / An improved primal simplex variant for pure processing networks by Chang (1989)
B. V. Cherkassky, 1992
B. V. Cherkassky, A. V. Goldberg, 1994, On Implementing Push-Relabel Method for the Maximum Flow Problem, Department of Computer Science, Stanford University (10.1007/3-540-59408-6_49)
10.1007/BF01415937 / ZOR—Methods Models Oper. Res. / Implementing Goldberg's max-flow algorithm—A computational investigation by Derigs (1989)
{'key': '10.1006/jagm.1995.0805_AL950805RF12', 'first-page': '260', 'article-title': 'Goldrmf/Goldnet-max-flow program', 'volume': '46', 'author': 'Derigs', 'year': '1990', 'journal-title': 'Europ. J. Oper Res.'} / Europ. J. Oper Res. / Goldrmf/Goldnet-max-flow program by Derigs (1990)
10.1145/363269.363610 / Commun. ACM / Algorithm 360: Shortest path forest with topological ordering by Dial (1969)
{'key': '10.1006/jagm.1995.0805_AL950805RF14', 'series-title': 'Flows in Networks', 'author': 'Ford', 'year': '1962'} / Flows in Networks by Ford (1962)
{'key': '10.1006/jagm.1995.0805_AL950805RF15', 'series-title': 'Network Flows and Matching: First DIMACS Implementation Challenge', 'first-page': '219', 'article-title': 'A speculative contraction method for the minimum cost flows: Toward a practical algorithm', 'author': 'Fujishige', 'year': '1993'} / Network Flows and Matching: First DIMACS Implementation Challenge / A speculative contraction method for the minimum cost flows: Toward a practical algorithm by Fujishige (1993)
10.1002/net.3230040302 / Networks / Implementation and computational comparison of primal, dual, and primal–dual computer codes for minimum cost network flow problem by Glover (1974)
A. V. Goldberg, 1985, A New Max-Flow Algorithm, Laboratory for Computer Science, M.I.T.
A. V. Goldberg, 1987, Efficient Graph Algorithms for Sequential and Parallel Computers
10.1137/S0097539792231179 / SIAM J. Comput. / Scaling algorithms for the shortest paths problem by Goldberg (1995)
A. V. Goldberg, R. Kennedy, 1993, An Efficient Cost Scaling Algorithm for the Assignment Problem, Department of Computer Science, Stanford University
{'key': '10.1006/jagm.1995.0805_AL950805RF21', 'series-title': 'Network Flows and Matching: First DIMACS Implementation Challenge', 'first-page': '157', 'article-title': 'On implementing scaling push-relabel algorithms for the minimum-cost flow problem', 'author': 'Goldberg', 'year': '1993'} / Network Flows and Matching: First DIMACS Implementation Challenge / On implementing scaling push-relabel algorithms for the minimum-cost flow problem by Goldberg (1993)
{'key': '10.1006/jagm.1995.0805_AL950805RF22', 'series-title': 'Flows, Paths, and VLSI Layout', 'first-page': '101', 'article-title': 'Network flow algorithms', 'author': 'Goldberg', 'year': '1990'} / Flows, Paths, and VLSI Layout / Network flow algorithms by Goldberg (1990)
10.1145/48014.61051 / J. Assoc. Comput. Mach. / A new approach to the maximum flow problem by Goldberg (1988)
10.1287/moor.15.3.430 / Math. Oper Res. / Finding minimum-cost circulations by successive approximation by Goldberg (1990)
10.1007/BFb0121089 / Math. Prog. Study / An efficient implementation of the network simplex method by Grigoriadis (1986)
{'key': '10.1006/jagm.1995.0805_AL950805RF26', 'series-title': 'Network Flows and Matching: First DIMACS Implementation Challenge', 'author': 'Johnson', 'year': '1993'} / Network Flows and Matching: First DIMACS Implementation Challenge by Johnson (1993)
{'key': '10.1006/jagm.1995.0805_AL950805RF27', 'series-title': 'Network Flows and Matching: First DIMACS Implementation Challenge', 'first-page': '267', 'article-title': 'A fast implementation of a path-following algorithm for maximizing a linear function over a network polytope', 'author': 'Joshi', 'year': '1993'} / Network Flows and Matching: First DIMACS Implementation Challenge / A fast implementation of a path-following algorithm for maximizing a linear function over a network polytope by Joshi (1993)
10.1007/BF01582905 / Math. Prog. / Computational results of an interior point algorithm for large scale linear programming by Karmarkar (1991)
{'key': '10.1006/jagm.1995.0805_AL950805RF29', 'series-title': 'Algorithms for Network Programming', 'author': 'Kennington', 'year': '1980'} / Algorithms for Network Programming by Kennington (1980)
10.1287/mnsc.20.5.814 / Management Sci. / A program for generating large scale capacitated assignment, transportation, and minimum cost flow network problems by Klingman (1974)
{'key': '10.1006/jagm.1995.0805_AL950805RF31', 'series-title': 'Network Flows and Matching: First DIMACS Implementation Challenge', 'first-page': '199', 'article-title': 'Performance Evaluation of MINET minimum cost netflow solver', 'author': 'Maros', 'year': '1993'} / Network Flows and Matching: First DIMACS Implementation Challenge / Performance Evaluation of MINET minimum cost netflow solver by Maros (1993)
10.1145/322063.322070 / J. Assoc. Comput. Mach. / Pivot strategies for primal-simplex network codes by Mulvey (1978)
{'key': '10.1006/jagm.1995.0805_AL950805RF33', 'series-title': 'Network Flows and Matching: First DIMACS Implementation Challenge', 'first-page': '19', 'article-title': 'Implementations of Goldberg–Tarjan maximum flow algorithm', 'author': 'Nguyen', 'year': '1993'} / Network Flows and Matching: First DIMACS Implementation Challenge / Implementations of Goldberg–Tarjan maximum flow algorithm by Nguyen (1993)
{'key': '10.1006/jagm.1995.0805_AL950805RF34', 'series-title': 'Network Flows and Matching: First DIMACS Implementation Challenge', 'first-page': '299', 'article-title': 'An efficient implementation of a network interior point method', 'author': 'Resende', 'year': '1993'} / Network Flows and Matching: First DIMACS Implementation Challenge / An efficient implementation of a network interior point method by Resende (1993)
{'key': '10.1006/jagm.1995.0805_AL950805RF35', 'series-title': 'Discrete Structures and Algorithms', 'first-page': '181', 'article-title': 'Scaling techniques for minimal cost network flows', 'author': 'Röck', 'year': '1980'} / Discrete Structures and Algorithms / Scaling techniques for minimal cost network flows by Röck (1980)
10.1007/BF02579369 / Combinatorica / A strongly polynomial minimum cost circulation algorithm by Tardos (1985)

Dates

Type	When
Created	22 years, 10 months ago (Oct. 6, 2002, 4:51 p.m.)
Deposited	5 years, 8 months ago (Dec. 17, 2019, 2:57 a.m.)
Indexed	3 months ago (May 16, 2025, 12:05 a.m.)
Issued	28 years, 7 months ago (Jan. 1, 1997)
Published	28 years, 7 months ago (Jan. 1, 1997)
Published Print	28 years, 7 months ago (Jan. 1, 1997)

Funders 0

None

BibTeX

@article{Goldberg_1997, title={An Efficient Implementation of a Scaling Minimum-Cost Flow Algorithm}, volume={22}, ISSN={0196-6774}, url={http://dx.doi.org/10.1006/jagm.1995.0805}, DOI={10.1006/jagm.1995.0805}, number={1}, journal={Journal of Algorithms}, publisher={Elsevier BV}, author={Goldberg, Andrew V}, year={1997}, month=jan, pages={1–29} }

JSON

{
  "indexed": {
    "date-parts": [
      [
        2025,
        5,
        16
      ]
    ],
    "date-time": "2025-05-16T04:05:11Z",
    "timestamp": 1747368311694
  },
  "reference-count": 36,
  "publisher": "Elsevier BV",
  "issue": "1",
  "license": [
    {
      "start": {
        "date-parts": [
          [
            1997,
            1,
            1
          ]
        ],
        "date-time": "1997-01-01T00:00:00Z",
        "timestamp": 852076800000
      },
      "content-version": "tdm",
      "delay-in-days": 0,
      "URL": "https://www.elsevier.com/tdm/userlicense/1.0/"
    }
  ],
  "content-domain": {
    "domain": [],
    "crossmark-restriction": false
  },
  "published-print": {
    "date-parts": [
      [
        1997,
        1
      ]
    ]
  },
  "DOI": "10.1006/jagm.1995.0805",
  "type": "journal-article",
  "created": {
    "date-parts": [
      [
        2002,
        10,
        6
      ]
    ],
    "date-time": "2002-10-06T20:51:01Z",
    "timestamp": 1033937461000
  },
  "page": "1-29",
  "source": "Crossref",
  "is-referenced-by-count": 283,
  "title": "An Efficient Implementation of a Scaling Minimum-Cost Flow Algorithm",
  "prefix": "10.1006",
  "volume": "22",
  "author": [
    {
      "given": "Andrew V",
      "family": "Goldberg",
      "sequence": "first",
      "affiliation": []
    }
  ],
  "member": "78",
  "reference": [
    {
      "key": "10.1006/jagm.1995.0805_AL950805RF1",
      "series-title": "Optimization. Handbooks in Operations Research and Management Science",
      "doi-asserted-by": "crossref",
      "DOI": "10.1016/S0927-0507(89)01005-4",
      "article-title": "Network flows",
      "author": "Ahuja",
      "year": "1989"
    },
    {
      "key": "10.1006/jagm.1995.0805_AL950805RF2",
      "series-title": "Network Flows and Matching: First DIMACS Implementation Challenge",
      "first-page": "1",
      "article-title": "Goldberg's algorithm for the maximum flow in perspective: A computational study",
      "author": "Anderson",
      "year": "1993"
    },
    {
      "key": "10.1006/jagm.1995.0805_AL950805RF3",
      "doi-asserted-by": "crossref",
      "unstructured": "D. P. Bertsekas, 1986, Distributed Asynchronous Relaxation Methods for Linear Network Flow Problems, Laboratory for Decision Systems, M.I.T.",
      "DOI": "10.1109/CDC.1986.267433"
    },
    {
      "key": "10.1006/jagm.1995.0805_AL950805RF4",
      "doi-asserted-by": "crossref",
      "first-page": "93",
      "DOI": "10.1287/opre.36.1.93",
      "article-title": "Relaxation methods for minimum cost ordinary and generalized network flow problems",
      "volume": "36",
      "author": "Bertsekas",
      "year": "1988",
      "journal-title": "Oper. Res."
    },
    {
      "key": "10.1006/jagm.1995.0805_AL950805RF5",
      "series-title": "Network Flows and Matching: First DIMACS Implementation Challenge",
      "first-page": "119",
      "article-title": "An empirical study of min cost flow algorithms",
      "author": "Bland",
      "year": "1993"
    },
    {
      "key": "10.1006/jagm.1995.0805_AL950805RF6",
      "doi-asserted-by": "crossref",
      "first-page": "1",
      "DOI": "10.1007/BF01586039",
      "article-title": "On the computational behavior of a polynomial-time network flow algorithm",
      "volume": "54",
      "author": "Bland",
      "year": "1992",
      "journal-title": "Math. Prog."
    },
    {
      "key": "10.1006/jagm.1995.0805_AL950805RF7",
      "doi-asserted-by": "crossref",
      "first-page": "1",
      "DOI": "10.1287/mnsc.24.1.1",
      "article-title": "Design and implementation of large scale transportation algorithms",
      "volume": "21",
      "author": "Bradley",
      "year": "1977",
      "journal-title": "Management Sci."
    },
    {
      "key": "10.1006/jagm.1995.0805_AL950805RF8",
      "doi-asserted-by": "crossref",
      "first-page": "64",
      "DOI": "10.1145/62038.62041",
      "article-title": "An improved primal simplex variant for pure processing networks",
      "volume": "15",
      "author": "Chang",
      "year": "1989",
      "journal-title": "ACM Trans. Math. Software"
    },
    {
      "key": "10.1006/jagm.1995.0805_AL950805RF9",
      "unstructured": "B. V. Cherkassky, 1992"
    },
    {
      "key": "10.1006/jagm.1995.0805_AL950805RF10",
      "doi-asserted-by": "crossref",
      "unstructured": "B. V. Cherkassky, A. V. Goldberg, 1994, On Implementing Push-Relabel Method for the Maximum Flow Problem, Department of Computer Science, Stanford University",
      "DOI": "10.1007/3-540-59408-6_49"
    },
    {
      "key": "10.1006/jagm.1995.0805_AL950805RF11",
      "doi-asserted-by": "crossref",
      "first-page": "383",
      "DOI": "10.1007/BF01415937",
      "article-title": "Implementing Goldberg's max-flow algorithm\u2014A computational investigation",
      "volume": "33",
      "author": "Derigs",
      "year": "1989",
      "journal-title": "ZOR\u2014Methods Models Oper. Res."
    },
    {
      "key": "10.1006/jagm.1995.0805_AL950805RF12",
      "first-page": "260",
      "article-title": "Goldrmf/Goldnet-max-flow program",
      "volume": "46",
      "author": "Derigs",
      "year": "1990",
      "journal-title": "Europ. J. Oper Res."
    },
    {
      "key": "10.1006/jagm.1995.0805_AL950805RF13",
      "doi-asserted-by": "crossref",
      "first-page": "632",
      "DOI": "10.1145/363269.363610",
      "article-title": "Algorithm 360: Shortest path forest with topological ordering",
      "volume": "12",
      "author": "Dial",
      "year": "1969",
      "journal-title": "Commun. ACM"
    },
    {
      "key": "10.1006/jagm.1995.0805_AL950805RF14",
      "series-title": "Flows in Networks",
      "author": "Ford",
      "year": "1962"
    },
    {
      "key": "10.1006/jagm.1995.0805_AL950805RF15",
      "series-title": "Network Flows and Matching: First DIMACS Implementation Challenge",
      "first-page": "219",
      "article-title": "A speculative contraction method for the minimum cost flows: Toward a practical algorithm",
      "author": "Fujishige",
      "year": "1993"
    },
    {
      "key": "10.1006/jagm.1995.0805_AL950805RF16",
      "doi-asserted-by": "crossref",
      "first-page": "191",
      "DOI": "10.1002/net.3230040302",
      "article-title": "Implementation and computational comparison of primal, dual, and primal\u2013dual computer codes for minimum cost network flow problem",
      "volume": "4",
      "author": "Glover",
      "year": "1974",
      "journal-title": "Networks"
    },
    {
      "key": "10.1006/jagm.1995.0805_AL950805RF17",
      "unstructured": "A. V. Goldberg, 1985, A New Max-Flow Algorithm, Laboratory for Computer Science, M.I.T."
    },
    {
      "key": "10.1006/jagm.1995.0805_AL950805RF18",
      "unstructured": "A. V. Goldberg, 1987, Efficient Graph Algorithms for Sequential and Parallel Computers"
    },
    {
      "key": "10.1006/jagm.1995.0805_AL950805RF19",
      "doi-asserted-by": "crossref",
      "first-page": "494",
      "DOI": "10.1137/S0097539792231179",
      "article-title": "Scaling algorithms for the shortest paths problem",
      "volume": "24",
      "author": "Goldberg",
      "year": "1995",
      "journal-title": "SIAM J. Comput."
    },
    {
      "key": "10.1006/jagm.1995.0805_AL950805RF20",
      "unstructured": "A. V. Goldberg, R. Kennedy, 1993, An Efficient Cost Scaling Algorithm for the Assignment Problem, Department of Computer Science, Stanford University"
    },
    {
      "key": "10.1006/jagm.1995.0805_AL950805RF21",
      "series-title": "Network Flows and Matching: First DIMACS Implementation Challenge",
      "first-page": "157",
      "article-title": "On implementing scaling push-relabel algorithms for the minimum-cost flow problem",
      "author": "Goldberg",
      "year": "1993"
    },
    {
      "key": "10.1006/jagm.1995.0805_AL950805RF22",
      "series-title": "Flows, Paths, and VLSI Layout",
      "first-page": "101",
      "article-title": "Network flow algorithms",
      "author": "Goldberg",
      "year": "1990"
    },
    {
      "key": "10.1006/jagm.1995.0805_AL950805RF23",
      "doi-asserted-by": "crossref",
      "first-page": "921",
      "DOI": "10.1145/48014.61051",
      "article-title": "A new approach to the maximum flow problem",
      "volume": "35",
      "author": "Goldberg",
      "year": "1988",
      "journal-title": "J. Assoc. Comput. Mach."
    },
    {
      "key": "10.1006/jagm.1995.0805_AL950805RF24",
      "doi-asserted-by": "crossref",
      "first-page": "430",
      "DOI": "10.1287/moor.15.3.430",
      "article-title": "Finding minimum-cost circulations by successive approximation",
      "volume": "15",
      "author": "Goldberg",
      "year": "1990",
      "journal-title": "Math. Oper Res."
    },
    {
      "key": "10.1006/jagm.1995.0805_AL950805RF25",
      "doi-asserted-by": "crossref",
      "first-page": "83",
      "DOI": "10.1007/BFb0121089",
      "article-title": "An efficient implementation of the network simplex method",
      "volume": "26",
      "author": "Grigoriadis",
      "year": "1986",
      "journal-title": "Math. Prog. Study"
    },
    {
      "key": "10.1006/jagm.1995.0805_AL950805RF26",
      "series-title": "Network Flows and Matching: First DIMACS Implementation Challenge",
      "author": "Johnson",
      "year": "1993"
    },
    {
      "key": "10.1006/jagm.1995.0805_AL950805RF27",
      "series-title": "Network Flows and Matching: First DIMACS Implementation Challenge",
      "first-page": "267",
      "article-title": "A fast implementation of a path-following algorithm for maximizing a linear function over a network polytope",
      "author": "Joshi",
      "year": "1993"
    },
    {
      "key": "10.1006/jagm.1995.0805_AL950805RF28",
      "doi-asserted-by": "crossref",
      "first-page": "555",
      "DOI": "10.1007/BF01582905",
      "article-title": "Computational results of an interior point algorithm for large scale linear programming",
      "volume": "52",
      "author": "Karmarkar",
      "year": "1991",
      "journal-title": "Math. Prog."
    },
    {
      "key": "10.1006/jagm.1995.0805_AL950805RF29",
      "series-title": "Algorithms for Network Programming",
      "author": "Kennington",
      "year": "1980"
    },
    {
      "key": "10.1006/jagm.1995.0805_AL950805RF30",
      "doi-asserted-by": "crossref",
      "first-page": "814",
      "DOI": "10.1287/mnsc.20.5.814",
      "article-title": "A program for generating large scale capacitated assignment, transportation, and minimum cost flow network problems",
      "volume": "20",
      "author": "Klingman",
      "year": "1974",
      "journal-title": "Management Sci."
    },
    {
      "key": "10.1006/jagm.1995.0805_AL950805RF31",
      "series-title": "Network Flows and Matching: First DIMACS Implementation Challenge",
      "first-page": "199",
      "article-title": "Performance Evaluation of MINET minimum cost netflow solver",
      "author": "Maros",
      "year": "1993"
    },
    {
      "key": "10.1006/jagm.1995.0805_AL950805RF32",
      "doi-asserted-by": "crossref",
      "first-page": "266",
      "DOI": "10.1145/322063.322070",
      "article-title": "Pivot strategies for primal-simplex network codes",
      "author": "Mulvey",
      "year": "1978",
      "journal-title": "J. Assoc. Comput. Mach."
    },
    {
      "key": "10.1006/jagm.1995.0805_AL950805RF33",
      "series-title": "Network Flows and Matching: First DIMACS Implementation Challenge",
      "first-page": "19",
      "article-title": "Implementations of Goldberg\u2013Tarjan maximum flow algorithm",
      "author": "Nguyen",
      "year": "1993"
    },
    {
      "key": "10.1006/jagm.1995.0805_AL950805RF34",
      "series-title": "Network Flows and Matching: First DIMACS Implementation Challenge",
      "first-page": "299",
      "article-title": "An efficient implementation of a network interior point method",
      "author": "Resende",
      "year": "1993"
    },
    {
      "key": "10.1006/jagm.1995.0805_AL950805RF35",
      "series-title": "Discrete Structures and Algorithms",
      "first-page": "181",
      "article-title": "Scaling techniques for minimal cost network flows",
      "author": "R\u00f6ck",
      "year": "1980"
    },
    {
      "key": "10.1006/jagm.1995.0805_AL950805RF36",
      "doi-asserted-by": "crossref",
      "first-page": "247",
      "DOI": "10.1007/BF02579369",
      "article-title": "A strongly polynomial minimum cost circulation algorithm",
      "volume": "5",
      "author": "Tardos",
      "year": "1985",
      "journal-title": "Combinatorica"
    }
  ],
  "container-title": "Journal of Algorithms",
  "original-title": [],
  "language": "en",
  "link": [
    {
      "URL": "https://api.elsevier.com/content/article/PII:S019667748570805X?httpAccept=text/xml",
      "content-type": "text/xml",
      "content-version": "vor",
      "intended-application": "text-mining"
    },
    {
      "URL": "https://api.elsevier.com/content/article/PII:S019667748570805X?httpAccept=text/plain",
      "content-type": "text/plain",
      "content-version": "vor",
      "intended-application": "text-mining"
    }
  ],
  "deposited": {
    "date-parts": [
      [
        2019,
        12,
        17
      ]
    ],
    "date-time": "2019-12-17T07:57:27Z",
    "timestamp": 1576569447000
  },
  "score": 1,
  "resource": {
    "primary": {
      "URL": "https://linkinghub.elsevier.com/retrieve/pii/S019667748570805X"
    }
  },
  "subtitle": [],
  "short-title": [],
  "issued": {
    "date-parts": [
      [
        1997,
        1
      ]
    ]
  },
  "references-count": 36,
  "journal-issue": {
    "issue": "1",
    "published-print": {
      "date-parts": [
        [
          1997,
          1
        ]
      ]
    }
  },
  "alternative-id": [
    "S019667748570805X"
  ],
  "URL": "http://dx.doi.org/10.1006/jagm.1995.0805",
  "relation": {},
  "ISSN": [
    "0196-6774"
  ],
  "subject": [],
  "container-title-short": "Journal of Algorithms",
  "published": {
    "date-parts": [
      [
        1997,
        1
      ]
    ]
  }
}