de.mpg.escidoc.pubman.appbase.FacesBean
Deutsch

Hilfe Wegweiser Impressum Kontakt Einloggen

# Datensatz

DATENSATZ AKTIONENEXPORT

Freigegeben

Forschungspapier

#### Lifting of Multicuts

##### MPG-Autoren
http://pubman.mpdl.mpg.de/cone/persons/resource/persons98382

Andres,  Björn
Computer Vision and Multimodal Computing, MPI for Informatics, Max Planck Society;

http://pubman.mpdl.mpg.de/cone/persons/resource/persons180806

Fuksova,  Andrea
Computer Vision and Multimodal Computing, MPI for Informatics, Max Planck Society;

http://pubman.mpdl.mpg.de/cone/persons/resource/persons201523

Lange,  Jan-Hendrik
Computer Vision and Multimodal Computing, MPI for Informatics, Max Planck Society;

##### Externe Ressourcen
Es sind keine Externen Ressourcen verfügbar
##### Volltexte (frei zugänglich)

1503.03791v5.pdf
(Preprint), 448KB

##### Ergänzendes Material (frei zugänglich)
Es sind keine frei zugänglichen Ergänzenden Materialien verfügbar
##### Zitation

Andres, B., Fuksova, A., & Lange, J.-H. (2016). Lifting of Multicuts. Retrieved from http://arxiv.org/abs/1503.03791.

For every simple, undirected graph $G = (V, E)$, a one-to-one relation exists between the decompositions and the multicuts of $G$. A decomposition of $G$ is a partition $\Pi$ of $V$ such that, for every $U \in \Pi$, the subgraph of $G$ induced by $U$ is connected. A multicut of $G$ is an $M \subseteq E$ such that, for every (chordless) cycle $C \subseteq E$ of $G$, $|M \cap C| \neq 1$. The multicut related to a decomposition is the set of edges that straddle distinct components. The characteristic function $x \in \{0, 1\}^E$ of a multicut $M = x^{-1}(1)$ of $G$ makes explicit, for every pair $\{v,w\} \in E$ of neighboring nodes, whether $v$ and $w$ are in distinct components. In order to make explicit also for non-neighboring nodes, specifically, for all $\{v,w\} \in E'$ with $E \subseteq E' \subseteq {V \choose 2}$, whether $v$ and $w$ are in distinct components, we define a lifting of the multicuts of $G$ to multicuts of $G' = (V, E')$. We show that, if $G$ is connected, the convex hull of the characteristic functions of those multicuts of $G'$ that are lifted from $G$ is an $|E'|$-dimensional polytope in $\mathbb{R}^{E'}$. We establish properties of trivial facets of this polytope.