A New Intersection Model and Improved Algorithms for Tolerance Graphs
From MaRDI portal
Publication:3058531
DOI10.1137/09075994XzbMath1207.05132MaRDI QIDQ3058531
Shmuel Zaks, George B. Mertzios, Ignasi Sau
Publication date: 3 December 2010
Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)
tolerance graphs; maximum clique; maximum weight independent set; minimum coloring; parallelogram graphs; intersection model
68R10: Graph theory (including graph drawing) in computer science
05C15: Coloring of graphs and hypergraphs
05C85: Graph algorithms (graph-theoretic aspects)
05C69: Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
05C62: Graph representations (geometric and intersection representations, etc.)
