• About communications
  • Current Issue
  • Digital Edition
  • Sample Issue
  • FAQs
  • Author Center
  • Author Guidelines
  • ACM Copyright Form
  • ACM Copyright Policy
  • ACM Author Rights
  • Submit a Video
  • Editor's Letters
  • Third-Party Material
  • Kudos Service
  • 2016 Editorial Calendar
  • Editorial Board
  • Editor's Letters
  • Editorial Staff
  • Contact Us
  • Mobile Apps
  • For Advertisers
  • Research Archive


    Latest Research Research Archive 2023DecemberNovemberOctoberSeptemberAugustJulyJuneMayAprilMarchFebruaryJanuary2022DecemberNovemberOctoberSeptemberAugustJulyJuneMayAprilMarchFebruaryJanuary2021DecemberNovemberOctoberSeptemberAugustJulyJuneMayAprilMarchFebruaryJanuary2020DecemberNovemberOctoberSeptemberAugustJulyJuneMayAprilMarchFebruaryJanuary2019DecemberNovemberOctoberSeptemberAugustJulyJuneMayAprilMarchFebruaryJanuary2018DecemberNovemberOctoberSeptemberAugustJulyJuneMayAprilMarchFebruaryJanuary2017DecemberNovemberOctoberSeptemberAugustJulyJuneMayAprilMarchFebruaryJanuary2016DecemberNovemberOctoberSeptemberAugustJulyJuneMayAprilMarchFebruaryJanuary2015DecemberNovemberOctoberSeptemberAugustJulyJuneMayAprilMarchFebruaryJanuary2014DecemberNovemberOctoberSeptemberAugustJulyJuneMayAprilMarchFebruaryJanuary2013DecemberNovemberOctoberSeptemberAugustJulyJuneMayAprilMarchFebruaryJanuary2012DecemberNovemberOctoberSeptemberAugustJulyJuneMayAprilMarchFebruaryJanuary2011DecemberNovemberOctoberSeptemberAugustJulyJuneMayAprilMarchFebruaryJanuary2010DecemberNovemberOctoberSeptemberAugustJulyJuneMayAprilMarchFebruaryJanuary2009DecemberNovemberOctoberSeptemberAugustJulyJuneMayAprilMarchFebruaryJanuary2008DecemberNovemberOctoberSeptemberAugustJulyJuneMayAprilMarchFebruaryJanuary Refine your search:
    Archives

    The Research archive provides access to all Research articles published in past issues of Communications of the ACM.

    December 2023


    From Communications of the ACM

    Technical Perspective: Maximum Flow through a Network: A Storied Problem and a Groundbreaking Solution

    Technical Perspective: Maximum Flow through a Network: A Storied Problem and a Groundbreaking Solution

    "Almost-Linear-Time Algorithms for Maximum Flow and Minimum-Cost Flow," by Li Chen et al., comes within striking distance of answering the question: "Does maximum flow have a scalable algorithm?"

    Shang-Hua Teng | December 2023

    From Communications of the ACM

    Almost-Linear-Time Algorithms for Maximum Flow and Minimum-Cost Flow

    Almost-Linear-Time Algorithms for Maximum Flow and Minimum-Cost Flow

    We present an algorithm that computes exact maximum flows and minimum-cost flows on directed graphs with m edges and polynomially bounded integral demands, costs, and capacities in m1+o(1) time.

    Li Chen, Rasmus Kyng, Yang P. Liu, Richard Peng, Maximilian Probst Gutenberg, Sushant Sachdeva | December 2023