4.7 Article

Accelerate minimum cut calculation by tree-cut mapping with local pruning

相关参考文献

注意:仅列出部分参考文献,下载原文获取全部文献信息。
Proceedings Paper Computer Science, Theory & Methods

Deterministic Mincut in Almost-Linear Time

Jason Li

Summary: This study presents a deterministic mincut algorithm for weighted, undirected graphs, answering a question from Karger. By partially derandomizing the Benczur-Karger graph sparsification technique and designing an efficient pessimistic estimator to capture graph cuts, as well as utilizing the expander decomposition framework, the researchers achieved the desired result. As a side-effect, a structural representation of all approximate mincuts in a graph was obtained, potentially useful for future applications.

STOC '21: PROCEEDINGS OF THE 53RD ANNUAL ACM SIGACT SYMPOSIUM ON THEORY OF COMPUTING (2021)

Article Engineering, Electrical & Electronic

STAG-Based QoS Support Routing Strategy for Multiple Missions Over the Satellite Networks

Tao Zhang et al.

IEEE TRANSACTIONS ON COMMUNICATIONS (2019)

Article Computer Science, Interdisciplinary Applications

Speed scaling on parallel processors with migration

Eric Angel et al.

JOURNAL OF COMBINATORIAL OPTIMIZATION (2019)

Article Telecommunications

SPLMax: Exploiting the Simple Path Introduced Locality for Maximum Flow Acceleration

Wei Wei et al.

IEEE COMMUNICATIONS LETTERS (2018)

Article Engineering, Electrical & Electronic

Power System Structural Vulnerability Assessment Based on an Improved Maximum Flow Approach

Jiakun Fang et al.

IEEE TRANSACTIONS ON SMART GRID (2018)

Article Computer Science, Information Systems

A maximum flow algorithm based on storage time aggregated graph for delay-tolerant networks

Hongyan Li et al.

AD HOC NETWORKS (2017)

Review Computer Science, Hardware & Architecture

Efficient Maximum Flow Algorithms

Andrew V. Goldberg et al.

COMMUNICATIONS OF THE ACM (2014)

Article Mathematics, Applied

Simplifying maximum flow computations: The effect of shrinking and good initial flows

F. Liers et al.

DISCRETE APPLIED MATHEMATICS (2011)