pith. sign in

arxiv: 1101.2061 · v1 · pith:SQY23P7Tnew · submitted 2011-01-11 · 💻 cs.DM

The graphs with the max-Mader-flow-min-multiway-cut property

classification 💻 cs.DM
keywords graphsmathcalalgorithmemphfunctionindependantmaximumminimum
0
0 comments X
read the original abstract

We are given a graph $G$, an independant set $\mathcal{S} \subset V(G)$ of \emph{terminals}, and a function $w:V(G) \to \mathbb{N}$. We want to know if the maximum $w$-packing of vertex-disjoint paths with extremities in $\mathcal{S}$ is equal to the minimum weight of a vertex-cut separating $\mathcal{S}$. We call \emph{Mader-Mengerian} the graphs with this property for each independant set $\mathcal{S}$ and each weight function $w$. We give a characterization of these graphs in term of forbidden minors, as well as a recognition algorithm and a simple algorithm to find maximum packing of paths and minimum multicuts in those graphs.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.