13 papers · ranked by Valyu relevance
Carolina Gallardo-Pavesi, Yaime Fernández, Javier E. Soto, Cecilia Hernández + 1 more
—Identifying the largest K flows in network traffic is an important task for applications such as flow scheduling and anomaly detection, which aim to improve network efficiency and security. However, accurately estimating flow frequencies is challenging due to the large number of flows and increasing network speeds.…
Jiaxin Jiang, Yunxiang Zhao, Lyu Xu, Byron Choi + 3 more
—Transaction flow networks are crucial in detecting illicit activities such as wash trading, credit card fraud, cashback arbitrage fraud, and money laundering. Our collaborator, Grab, a leader in digital payments in Southeast Asia, faces increasingly sophisticated fraud patterns in its transaction flow networks. In…
Shruthi Kannappan, Ashwina Kumar, Rupesh Nasre
MaxFlow is a fundamental problem in graph theory and combinatorial optimisation, used to determine the maximum flow from a source node to a sink node in a flow network. It finds applications in diverse domains, including computer networks, transportation, and image segmentation. The core idea is to maximise the total…
Shruthi Kannappan, Ashwina Kumar, Rupesh Nasre
The Maximum Flow (Max-Flow) problem is a cornerstone in graph theory and combinatorial optimization, aiming to determine the largest possible flow from a designated source node to a sink node within a capacitated flow network. It has extensive applications across diverse domains such as computer networking…
Shridharan Chandramouli
| 1 | | Introduction | | | |---|-----------------------------------------------------|---------------------------------------------------------------------------|----|--| | | 1.1 | Motivation | 1 | | | | 1.2 | Proper Order Multi-Column Graph Structure | 2 | | | | 1.3 | General Maxflow/Mincut Problem Definition | 2 | |…
Wolfgang Bangerth
Digital elevation models (DEMs) have reached resolutions and sizes that only parallel computaters can efficiently process. One important application of DEMs is predicting how much water flows where, the so-called ``flow routing problem'' (a variation of which is the problem of determining the drainage area upstream of…
Mohammad Abdulaziz, Thomas Ammer
We present formalisations of the correctness of executable algorithms to solve minimum-cost flow problems in Isabelle/HOL. Two of the algorithms are based on the technique of scaling, most notably Orlin's algorithm, which has the fastest known running time for solving the problem of minimum-cost flow. We also include a…
Eleanor Wiesler, Trace Baxley
We propose a learning-augmented framework for accelerating max-flow computation and image segmentation by integrating Graph Neural Networks (GNNs) with the Ford-Fulkerson algorithm. Rather than predicting initial flows, our method learns edge importance probabilities to guide augmenting path selection. We introduce a…
Jason Li
We present a randomized augmenting paths-based algorithm to compute the maximum flow in a directed, uncapacitated graph in almost $m+nF$ time, matching the algorithm of Karger and Levine for undirected graphs (SICOMP 2015). Combined with an initial $\sqrt n$ rounds of blocking flow to reduce the value of $F$, we obtain…
Bernhard Haeupler, Yonggang Jiang, Yun‐Ze Long, Thatchaphol Saranurak + 1 more
We present a parallel algorithm for computing (1 + ϵ)-approximate mincost flow on an undirected graph with m edges, where capacities and costs are assigned to both edges and vertices. Our algorithm achieves Oˆ(m) work and Oˆ(1) depth when ϵ > 1/polylog(m), making both the work and depth almost optimal, up to a…
Joan Vendrell Gallart, Russell Bent, Solmaz S. Kia
This paper considers an optimal radial reconfiguration problem in multi-source distribution networks, where the goal is to find a radial configuration that minimizes quadratic distribution costs while ensuring all sink demands are met. This problem arises in critical infrastructure systems such as power distribution…
Patthadon Tantiameorn, Grittin Nuntasombat, Jittat Fakcharoenphol
Sketch data structures are very useful for computing statistics on streaming data, including network traffic, server requests, and financial transactions. In recent work, FermatSketch was introduced as an underlying data structure used to monitor changes in network states. It is a linear data structure that maintains…
Arman Mollakhani, Pieter Wuille, Dongning Guo
In the Bitcoin system, transactions arrive continuously at miners' mempools and await inclusion in future blocks. Every non-coinbase transaction must spend one or more unspent outputs created by previous transactions, inducing dependency constraints among transactions in the mempool. At the same time, miners are…