de.mpg.escidoc.pubman.appbase.FacesBean
Deutsch
 
Hilfe Wegweiser Impressum Kontakt Einloggen
  DetailsucheBrowse

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.


Zitierlink: http://hdl.handle.net/11858/00-001M-0000-0028-DCA9-7
Zusammenfassung
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.