{"id":"arxiv:2409.08350","kind":"preprint","title":"An efficient heuristic for approximate maximum flow computations","authors":["Jingyun Qian","Georg Hahn"],"author_count":2,"year":2024,"published":"2024-09-12","venue":null,"cited_by":0,"doi":null,"arxiv_id":"2409.08350","nct_id":null,"source_url":"https://arxiv.org/abs/2409.08350","archive_url":"https://space-kitty.com/papers/arxiv:2409.08350","updated":"2024-09-12","pmid":null,"pmcid":null,"openalex_id":"W4403661643","pdf_url":"https://arxiv.org/pdf/2409.08350","abstract":"Several concepts borrowed from graph theory are routinely used to better understand the inner workings of the (human) brain. To this end, a connectivity network of the brain is built first, which then allows one to assess quantities such as information flow and information routing via shortest path and maximum flow computations. Since brain networks typically contain several thousand nodes and edges, computational scaling is a key research area. In this contribution, we focus on approximate maximum flow computations in large brain networks. By combining graph partitioning with maximum flow computations, we propose a new approximation algorithm for the computation of the maximum flow with runtime O(|V||E|^2/k^2) compared to the usual runtime of O(|V||E|^2) for the Edmonds-Karp algorithm, where $V$ is the set of vertices, $E$ is the set of edges, and $k$ is the number of partitions. We assess both accuracy and runtime of the proposed algorithm on simulated graphs as well as on graphs downloaded from the Brain Networks Data Repository (https://networkrepository.com).","abstract_license":"CC0-1.0 (arXiv descriptive metadata)","license":null,"is_open_access":false,"retracted":false,"peer_reviewed":false,"categories":["cs.DS","stat.ME"],"details":null,"provenance":"arxiv","attribution":"Abstract: arXiv descriptive metadata (CC0). Thank you to arXiv for use of its open access interoperability. This service was not reviewed or approved by, nor does it necessarily express or reflect the policies or opinions of, arXiv.","topics":[{"slug":"algorithms-complexity","name":"Algorithms & Complexity Breakthroughs","domain_slug":"math-cs"}],"cited_in_dossiers":[]}