The Recognition of Tolerance and Bounded Tolerance Graphs

DOI10.1137/090780328zbMath1235.05098OpenAlexW1954157972WikidataQ106203067 ScholiaQ106203067MaRDI QIDQ3115865

Ignasi Sau, George B. Mertzios, Shmuel Zaks

Publication date: 11 February 2012

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: http://dro.dur.ac.uk/9046/1/9046.pdf

zbMATH Keywords

overlaptolerance graphstrapezoid graphsNP-completepermutation graphsvertex splittingrecognition algorithmrecognition problemsbounded tolerance graphsinterval relationssubclass of perfect graphs

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Graph representations (geometric and intersection representations, etc.) (05C62) Perfect graphs (05C17)

Related Items (9)

A Linear-Time Algorithm for Maximum-Cardinality Matching on Cocomparability Graphs ⋮ Recognizing simple-triangle graphs by restricted 2-chain subgraph cover ⋮ A recognition algorithm for simple-triangle graphs ⋮ On the intersection of tolerance and cocomparability graphs ⋮ The recognition of triangle graphs ⋮ An intersection model for multitolerance graphs: efficient algorithms and hierarchy ⋮ A characterization of interval orders with semiorder dimension two ⋮ New Geometric Representations and Domination Problems on Tolerance and Multitolerance Graphs ⋮ The Recognition of Simple-Triangle Graphs and of Linear-Interval Orders is Polynomial

This page was built for publication: The Recognition of Tolerance and Bounded Tolerance Graphs