Iskanje po repozitoriju

Opis: The set of relevant cuts in a graph is the union of all minimum weight bases of the cut space. We show that a cut is relevant if and only if it is a minimum weight cut between two distinct vertices. Moreover, we give a characterization in terms of Picard-Queyranne Directed Acyclic Graphs that can be used to accelerate the enumeration of the relevant cuts. Finally, we perform an experimental evaluation by comparing with state-of-the-art algorithms.
Ključne besede: cut Space, matroid, Gomory-Hu tree, enumeration
Objavljeno v RUP: 23.09.2026; Ogledov: 207; Prenosov: 4
Celotno besedilo (721,59 KB)