Answers are grounded in this paper and cite their sources.
Computer networks are often multi-layered. For simplicity, let us focus on two-layered networks with logical layer and physical layer. Such a network can be modeled as a labeled graph$G = (V, E)$with a label setL = \ ₁, ₂, , q \, in which each edge (denotes logical connection)e ∈ Ehas a label (denotes physical link)(e)from L. The key issue is that different edges may have the same label. In the weighted minimum Label s-t Cut problem, we are given a labeled graph$G=(V,E)$with label set L, where each labelhas a nonnegative weightw, a sources ∈ Vand a sinkt ∈ V. The problem asks to find a minimum weight label subset$L'$(called a label s-t cut) such that the removal of all edges with labels in$L'$disconnects s and t. Label s-t cut depicts the connectivity bottleneck of a layered network. It is a natural generalization of the edge connectivity of a graph. In this paper, we provide an approximation algorithm for the weighted Label s-t Cut problem with ratioO(n2/3), where n is the number of vertices. This is the first approximation algorithm for the problem whose ratio is given in terms of n. The key point of the algorithm is a mechanism to interpret label weight on an edge as both its length (as in the Shortest s-t Path problem) and capacity (as in the Min s-t Cut problem). Experiments on random graphs show that the algorithm has also good practical performance.
No takes yet. Share an insight, caveat, or question.
A 2024 study studied this question.
Synapse has enriched 10 related papers. Consider them for comparative context: