Open Access. Powered by Scholars. Published by Universities.®
Physical Sciences and Mathematics Commons™
Open Access. Powered by Scholars. Published by Universities.®
Articles 1 - 2 of 2
Full-Text Articles in Physical Sciences and Mathematics
Some Aspects Of The Semi-Perfect Elimination, Stephan Olariu
Some Aspects Of The Semi-Perfect Elimination, Stephan Olariu
Computer Science Faculty Publications
Several efficient algorithms have been proposed to construct a perfect elimination ordering of the vertices of a chordal graph. We study the behaviour of two of these algorithms in relation to a new concept, namely the semi-perfect elimination ordering, which provides a natural generalization of chordal graphs.
On A Unique Tree Representation For P4-Extendible Graphs, B. Jamison, S. Olariu
On A Unique Tree Representation For P4-Extendible Graphs, B. Jamison, S. Olariu
Computer Science Faculty Publications
Several practical applications in computer science and computational linguistics suggest the study of graphs that are unlikely to have more than a few induced paths of length three. These applications have motivated the notion of a cograph, defined by the very strong restriction that no vertex may belong to an induced path of length three. The class of P4-extendible graphs that we introduce in this paper relaxes this restriction, and in fact properly contains the class of cographs, while still featuring the remarkable property of admitting a unique tree representation. Just as in the case of cographs, the …