Pairwise Compatibility Graphs: A Survey - Archive ouverte HAL Access content directly
Journal Articles SIAM Review Year : 2016

Pairwise Compatibility Graphs: A Survey


A graph $G=(V,E)$ is a pairwise compatibility graph (PCG) if there exists an edge-weighted tree $T$ and two nonnegative real numbers $d_{min}$ and $d_{max}$ such that each leaf $u$ of $T$ is a node of $V$ and there is an edge $(u,v) \in E$ if and only if $d_{min} \leq d_T (u, v) \leq d_{max}$, where $d_T (u, v)$ is the sum of weights of the edges on the unique path from $u$ to $v$ in $T$. In this article, we survey the state of the art concerning this class of graphs and some of its subclasses.
Fichier principal
Vignette du fichier
SurveyPCG.pdf (537.67 Ko) Télécharger le fichier
Origin : Files produced by the author(s)

Dates and versions

hal-01388533 , version 1 (29-05-2017)



Tiziana Calamoneri, Blerina Sinaimeri. Pairwise Compatibility Graphs: A Survey. SIAM Review, 2016, 58 (3), pp.445 - 460. ⟨10.1137/140978053⟩. ⟨hal-01388533⟩
125 View
617 Download



Gmail Facebook Twitter LinkedIn More