Parallel Algorithm For Finding The Minimum s − t s-t Cut in a Structured 3-Dimensional Proper Order Graph
Shridharan Chandramouli · 2026
Read Parallel Algorithm For Finding The Minimum s − t s-t Cut in a Structured 3-Dimensional Proper Order Graph by Shridharan Chandramouli (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2601-17026.txt.
Introduction
Shridharan Chandramouli splits a hard cut task for fast work on many cores. The task finds the least cut twixt two points in a graph. Such cuts drive cuts of 3D scans in care work. Big 3D graphs make lone-core cuts crawl. His 2026 preprint builds a fast path for a clean class of 3D graphs.
Those graphs stack in a set, rank-kept form. The fast path splits the cut hunt across cores. Each core takes a slice of the graph grid. Fast true cuts could speed scan work in clinics. They may also aid chip and net layout tasks.
Catalog record
| CREATOR | Shridharan Chandramouli |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 53 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2601-17026
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Parallel Algorithm For Finding The Minimum s − t s-t Cut in a Structured 3-Dimensional Proper Order Graph Shridharan Chandramouli Abstract Project Advisory Committee: Prof. Ross Whitaker (chair) Prof. Martin Berzins Prof. Suresh Venkatasubramanian 1 Introduction The problem that we aim to solve is that of parallelizing the s-t mincut/maxflow problem for large structured 3D proper ordered graphs in order to improve the performance of current image volume segmentation algorithms. The graph cuts algorithm have been used quite extensively in computer vision and in image processing as a tool for solving energy minimization problems. One of the first uses of graph cuts for computer vision problems was through the work of Greig, Porteous and Seheult where graph cuts were shown to solve the maximum a posteriori estimation of a binary image in the context of image smoothing by finding the maximum flow through an associated image network. We are interested in the image segmentation problem viewed as a surface estimation problem applied to segmentation of horizons in geological images. Wu and Chen in [ 16 ] studied the image segmentation problem and gave the basis for solving the energy minimization problem applied to image segmentation as solving the maxflow problem in a multi-column proper order graph. These proper order graphs are structured graphs arranged as multiple columns in a 3D space with edges from nodes in a column to nodes in its adjacent columns. While there have been many generalized algorithms for solving the maxflow problem, the large size of the image volume and a correspondingly large graph structure often make these algorithms too slow for practical applications. In this project we create a parallelization scheme to solve the maxflow problem for this special graph structure that both improves the running time of these algorithms and reduces the memory footprint of the algorithm by using implicit addressing schemes. 1.1 Motivation Image segmentation is one of the most widely studied problems that occur frequently in medical imaging and computer vision problems. The use of graph cuts for pixel classification was popularized by Boykov and Jolly in [ 4 ] where they used proposed a new technique for general purpose interactive segmentation of N-dimensional images that gave globally optimal solutions. They posed the problem as an energy minimization problem where the total energy minimized was a sum of the region energy, which represented the relative importance of the region properties, and a boundary term, which was a penalty for a discontinuity in the labeling across neighbors in the image. Wu and Chen extended the idea of image segmentation to surface extraction problems in [ 16 ] . The energy minimization scheme with respect to the surface \mathcal{S} and the corresponding cost function is given by \displaystyle E(\mathcal{S})=E_{feature}(\mathcal{S})+E_{prior}(\mathcal{S}) (1) Here \mathcal{S} is defined over a special graph structure whose vertices are arranged in the form of multiple columns. E_{feature}(\mathcal{S}) represents the feature matching term that quantifies the desired feature along columns and E_{prior}(\mathcal{S}) is the prior term that encodes shape and smoothness information in the form of interaction between columns. Wu and Chen designed a special geometric graph in the form of a multi-column proper-ordered graph. By using such a graph, they proved the equivalence between the energy minimization problem and min-cut on the s-t graph via optimal net surface problems, thus providing a globally optimal and efficient solution. These surface-net problems induce costs on surfaces rather than regions. The graph construction is discussed in detail in the next section. The min-cut/maxflow algorithms, while having polynomial running time, are still not scalable with the size of the image for practical applications. One of the applications is the use of this algorithm to segment horizons in seismic image volumes. These volumes typically tend to contain anywhere between 10-100 million nodes, and the current serial algorithm tends to take a few hours to complete. Furthermore, the unstructured implementations often fail to take advantage of the graph structure and leads to a significant memory requirement in the order of a few tens of gigabytes. We therefore require a effective parallel strategy that can both be scalable and uses an implicit addressing scheme that uses considerable lesser memory. 1.2 Proper Order Multi-Column Graph Structure The proper ordered graph is a structured multi-column graph \mathcal{G}=(\mathcal{V},\mathcal{E}) with a set of costs on the vertices \mathcal{V} and the edges \mathcal{E} . For a multi-column graph, the vertices are arranged logically as a collection of approximately parallel columns, with each column comprising the same number of vertices. A net surface \mathcal{N} is defined by a bijective function in a multi-column graph such that \mathcal{N} intersects with each column at exactly one vertex. A proper order graph also has the following structure. Each column vertex is connected to a sequence of consecutive vertices from each of the adjacent columns. The set of vertices that a column vertex is connected to is called the edge interval of that vertex. For any two consecutive vertices in a column, the first/last edge in the edge interval of a vertex must be above/below or equal to the first/last edge of the vertex below it. For the surface extraction, we are interested in the optimal VCE-weight net surface problem, where each vertex v\in\mathcal{V} in a graph carries a real-valued weight w(v) and each edge e\in\mathcal{E} holds a real valued cost c(e) while maintaining convexity among the edges of an edge interval. Then the optimal surface is a net \mathcal{N} in \mathcal{G} such that \sum_{v\in\mathcal{V}(\mathcal{N})}w(v)+\sum_{e\in\mathcal{E}(\mathcal{N})}c(e) . The graph is then converted to a s-t graph by adding two additional vertices s and t which form the source and sink respectively. The weights on the nodes w(v) are correspondingly converted to the costs associated with the edges connecting the node v to the source or the sink. The figure in 1 shows the edge structure between adjacent columns in the proper order graph. Figure 1: Figure shows the proper order edge structure between adjacent columns in the graph. Each node is connected to the immediate node above and below it and a set of vertices in its adjacent column. The number of connections depends on the edge interval. The figure on left has an edge interval of 2 where as the figure on the right has an edge interval of 3. Figure 2: A simplified 3D proper order graph structure 1.3 General Maxflow/Mincut Problem Definition Let G = (V, E) be a directed connected graph with vertex set V and edge set E. Let n and m be the size of the vertex set V and the edge set E respectively. We call G a flow network if it has two distinguished vertices, a source s and a sink t , and a positive capacity c(v,w) on each directed edge (v,w). A flow f on G is a real-valued function on vertex pairs satisfying the conditions below. \displaystyle f(v,w) \displaystyle\leq c(v,w)\hskip 20.00003pt\forall(v,w)\in E (2) \displaystyle f(v,w) \displaystyle=-f(w,v) (3) \displaystyle\sum\limits_{u}f(u,v) \displaystyle=0\hskip 20.00003pt\forall v\in V-{s,t} (4) The antisymmetry constrain (2), used by Sleator [ 14 ] is for (i) eliminate both edge having positive flow values and (ii) simplifies the formal expressions of constraints. The value of a flow f is the net flow into the sink, |f|=\sum\nolimits_{v\in V}f(v,t) (5) A