|
| | | | |
| | | |
| Stat |
Members: 3645
Articles: 2'506'133
Articles rated: 2609
27 April 2024 |
|
| | | | |
|
Article overview
| |
|
|
The graphs with the max-Mader-flow-min-multiway-cut property | | Guyslain Naves
; Vincent Jost
; | | Date: |
11 Jan 2011 | | Abstract: | We are given a graph $G$, an independant set $mathcal{S} subset V(G)$ of
emph{terminals}, and a function $w:V(G) o 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. | | Source: | arXiv, 1101.2061 | | Services: | Forum | Review | PDF | Favorites | |
|
|
No review found.
Did you like this article?
Note: answers to reviews or questions about the article must be posted in the forum section.
Authors are not allowed to review their own article. They can use the forum section.
browser Mozilla/5.0 AppleWebKit/537.36 (KHTML, like Gecko; compatible; ClaudeBot/1.0; +claudebot@anthropic.com)
|
| |
|
|
|
|
News, job offers and information for researchers and scientists:
| |
REGISTER