A note on tolerance graph recognition

DOI10.1016/J.DAM.2003.08.012MaRDI QIDQ1887065zbMATH OpenOpenAlexFDO

Authors Ryan Hayward, Ron Shamir

Publication date 23 November 2004

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.dam.2003.08.012

zbMATH Keywords

class NP tolerance representation

Mathematics Subject Classification ID

Graph representations (geometric and intersection representations, etc.) (05C62)

Review text

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)].

Recommendations

Cited in

(3)

This page was built for publication: A note on tolerance graph recognition

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1887065)