Pairwise Compatibility Graphs: A Survey

Abstract : 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.
Document type :
Journal articles
Complete list of metadatas

Cited literature [54 references]  Display  Hide  Download

https://hal.inria.fr/hal-01388533
Contributor : Marie-France Sagot <>
Submitted on : Monday, May 29, 2017 - 10:26:44 AM
Last modification on : Thursday, November 21, 2019 - 2:10:51 AM
Long-term archiving on : Wednesday, September 6, 2017 - 10:30:10 AM

File

SurveyPCG.pdf
Files produced by the author(s)

Identifiers

Collections

Citation

Tiziana Calamoneri, Blerina Sinaimeri. Pairwise Compatibility Graphs: A Survey. SIAM Review, Society for Industrial and Applied Mathematics, 2016, 58 (3), pp.445 - 460. ⟨10.1137/140978053⟩. ⟨hal-01388533⟩

Share

Metrics

Record views

186

Files downloads

409