A New Intersection Model and Improved Algorithms for Tolerance Graphs

DOI10.1007/978-3-642-11409-0_25zbMath1273.05152MaRDI QIDQ5851113

Shmuel Zaks, George B. Mertzios, Ignasi Sau

Publication date: 21 January 2010

Published in: Graph-Theoretic Concepts in Computer Science (Search for Journal in Brave)

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

zbMATH Keywords

tolerance graphs; maximum clique; maximum weight independent set; minimum coloring; parallelogram graphs; intersection model

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

05C85: Graph algorithms (graph-theoretic aspects)

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