Papers for

software developers for graph analytics

Papers whose findings have a practical use for this group, as judged from the abstract. Open a paper to read what it means in practice.

Deterministic algorithm improves global minimum cut queries to n to the three halves

Deterministic Global Minimum Cut Using $\tilde{O}(n^{3/2})$ Cut Queries

Abstract: Finding a global minimum cut in an unweighted graph is a fundamental task in the cut-query model. While there exists a randomized algorithm for this task using $\tilde O(n)$ queries, known deterministic algorithms use $\tilde{O}(n^{5/3})$ queries. We improve upon this result and give a simple deterministic algorithm that finds a global minimum cut using $\tilde O(\min\left\{ nδ,n^2/δ\right\})$ cut queries, which equals $\tilde{O}(n^{3/2})$ in the worst case, where $δ$ is the minimum degree of the graph. The key ingredient in our approach is an efficient maximum $s,t$-flow algorithm, for the case when the minimum $s,t$-cut has value at most $δ$.

Fri 16 OctData Structures and Algorithms

The gist

Finding the smallest set of edges that splits a network into two parts is a key problem in computer science. There is a fast but random method to do this, and slower methods that always work but take more tries. The authors created a new approach that is always reliable and faster than old deterministic methods, using fewer checks on the network connections. They use a special trick involving network flow calculation to achieve this improvement.

Open → 2610.23461v1