A note on tolerance graph recognition (Q1887065): Difference between revisions
From MaRDI portal
ReferenceBot (talk | contribs) Changed an Item |
Normalize DOI. |
||
| Property / DOI | |||
| Property / DOI: 10.1016/j.dam.2003.08.012 / rank | |||
| Property / DOI | |||
| Property / DOI: 10.1016/J.DAM.2003.08.012 / rank | |||
Normal rank | |||
Latest revision as of 11:43, 16 December 2024
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | A note on tolerance graph recognition |
scientific article |
Statements
A note on tolerance graph recognition (English)
0 references
23 November 2004
0 references
A graph \(G=(V,E)\) is a tolerance graph if there is a set \(I=\{I_v\mid v\in V\}\) of closed real intervals and a set \(\tau=\{\tau_v\mid v\in V\}\) of positive real numbers such that \((X,Y)\in E\) if and only if \(|I_x\cap I_y|\geq \min\{\tau_x,\tau_y\}\), see [\textit{M. C. Golumbic, C. L. Monma} and \textit{W. T. Trotter} jun., Discrete Appl. Math. 9, 157--170 (1984; Zbl 0547.05054)].
0 references
tolerance representation
0 references
class NP
0 references
