We present two Massively Parallel Computation (MPC) algorithms for the Minimum Cut problem: an O(1)-round exact algorithm with Õ(n) memory per machine, and an O(log n · log log n) round (2 + ε) approximation with Õ(nα) memory per machine, for any positive constant α < 1. Both algorithms use Õ(m) global memory. © 2020 Association for Computing Machinery
AbstractGiven a connected undirected multigraph with n vertices and m edges, we first propose a new ...
1. Introduction. Over the last decade, massive parallelism became a major paradigm in computing, and...
In this paper, we present an efficient implementation of the O(mn + n&sup2; log n) time algorith...
We study the Weighted Min Cut problem in the Adaptive Massively Parallel Computation (AMPC) model. I...
We present O(log log n)-round algorithms in the Massively Parallel Computation (MPC) model, with a(n...
Over the past decade, there has been increasing interest in distributed/parallel algorithms for proc...
We present the first near-linear work and poly-logarithmic depth algorithm for computing a minimum c...
We deal with the maximum cut problem on cubic graphs and we present a simple O(log n) time parallel ...
For over a decade now we have been witnessing the success of massive parallel computation (MPC) fram...
We present O(log log n) round scalable Massively Parallel Computation algorithms for maximal indepen...
We significantly improve known time bounds for solving the minimum cut problem on undirected graphs....
We present a practically efficient algorithm that finds all global minimum cuts in huge undirected g...
Abstract This paper presents a new approach to nding minimum cuts in undirected graphs. The fundamen...
We signicantly improve known time bounds for solving the minimum cut problem on undirected graphs. W...
This paper is concerned with the maximum cut problem in parallel on cubic graphs. New theoretical re...
AbstractGiven a connected undirected multigraph with n vertices and m edges, we first propose a new ...
1. Introduction. Over the last decade, massive parallelism became a major paradigm in computing, and...
In this paper, we present an efficient implementation of the O(mn + n&sup2; log n) time algorith...
We study the Weighted Min Cut problem in the Adaptive Massively Parallel Computation (AMPC) model. I...
We present O(log log n)-round algorithms in the Massively Parallel Computation (MPC) model, with a(n...
Over the past decade, there has been increasing interest in distributed/parallel algorithms for proc...
We present the first near-linear work and poly-logarithmic depth algorithm for computing a minimum c...
We deal with the maximum cut problem on cubic graphs and we present a simple O(log n) time parallel ...
For over a decade now we have been witnessing the success of massive parallel computation (MPC) fram...
We present O(log log n) round scalable Massively Parallel Computation algorithms for maximal indepen...
We significantly improve known time bounds for solving the minimum cut problem on undirected graphs....
We present a practically efficient algorithm that finds all global minimum cuts in huge undirected g...
Abstract This paper presents a new approach to nding minimum cuts in undirected graphs. The fundamen...
We signicantly improve known time bounds for solving the minimum cut problem on undirected graphs. W...
This paper is concerned with the maximum cut problem in parallel on cubic graphs. New theoretical re...
AbstractGiven a connected undirected multigraph with n vertices and m edges, we first propose a new ...
1. Introduction. Over the last decade, massive parallelism became a major paradigm in computing, and...
In this paper, we present an efficient implementation of the O(mn + n&sup2; log n) time algorith...
DOI
Add to ORKG