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

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

2011-01-11

arxiv.org/abs/1101.2061v1

Computer Science

Discrete Mathematics

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

The graphs with the max-Mader-flow-min-multiway-cut property does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with The graphs with the max-Mader-flow-min-multiway-cut property, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The graphs with the max-Mader-flow-min-multiway-cut property will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-160203