Completeness for intersection classes |
| |
Authors: | Timothy B. Moorhouse Derek G. Corneil |
| |
Affiliation: | Department of Computer Science, University of Toronto, Toronto, Ontario, Canada M5S 1A4 |
| |
Abstract: | An intersection representation of a graph is a function gf mapping vertices to sets such that for any u ≠ v, u is adjacent to v iff gf(u) ∩ gf(v) ≠ . The intersection class defined by a set of sets ∑ is the set of all graphs having an intersection representation using sets from ∑. Interval graphs and chordal graphs are well-studied examples of intersection classes.This paper introduces the notion of completeness for intersection classes. That is, determining precisely what restrictions can be made on the allowable sets without losing the power to represent any graph in the intersection class. The solution to this problem is presented for the chordal graphs. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|