A New Intersection Model and Improved Algorithms for Tolerance Graphs

DOI10.1137/09075994XzbMath1207.05132OpenAlexW2130950293MaRDI QIDQ3058531

George B. Mertzios, Shmuel Zaks, Ignasi Sau

Publication date: 3 December 2010

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/09075994x

zbMATH Keywords

tolerance graphsmaximum cliquemaximum weight independent setminimum coloringparallelogram graphsintersection model

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Graph representations (geometric and intersection representations, etc.) (05C62)

Related Items (5)

A Linear-Time Algorithm for Maximum-Cardinality Matching on Cocomparability Graphs ⋮ On the intersection of tolerance and cocomparability graphs ⋮ Counting independent sets in a tolerance graph ⋮ An intersection model for multitolerance graphs: efficient algorithms and hierarchy ⋮ New Geometric Representations and Domination Problems on Tolerance and Multitolerance Graphs

This page was built for publication: A New Intersection Model and Improved Algorithms for Tolerance Graphs