Academic Research Library

Find some of the best Journals and Proceedings.

On Minimal Cuts in Ladder Graphs

Author : Mark Korenblit

Abstract :In this paper, we consider a ladder graph, denoted by Ln , which represents a planar graph with 2n vertices and 3n – 2 edges. It can be visualized as a "ladder" with n rungs, formed by connecting two parallel paths of length n with n additional edges (the rungs). We study minimal cuts (min-cuts), defined as minimal sets of edges whose removal disconnects the target from the source, in ladder graphs. The deletion of any edge from a min-cut turns it into a non-cut. We explore the structure of min-cuts in both directed and undirected versions of a ladder graph and estimate their number and sizes. We show that Ln has n2 min-cuts of sizes from 2 to n and demonstrate the distribution of the min-cuts by their sizes. In addition, using the above results, we estimate the time complexity of the algorithm that computes st-connectedness for a probabilistic directed ladder graph (the probability that there exists a path of operating edges between the source and the target in the graph). The running time of this algorithm for a directed Ln is O(n5).

Keywords :Ladder graph, min-cut, probabilistic graph, st-connectedness.

Conference Name :International Conference on Discrete Applied Mathematics and Mathematical Programming (ICDAMMP-25)

Conference Place Jerusalem, Israel

Conference Date 23rd Jul 2025

Preview