Open Access. Powered by Scholars. Published by Universities.®
Physical Sciences and Mathematics Commons™
Open Access. Powered by Scholars. Published by Universities.®
Articles 1 - 3 of 3
Full-Text Articles in Physical Sciences and Mathematics
A Mergeable Double-Ended Priority Queue, S. Olariu, Z. Wen
A Mergeable Double-Ended Priority Queue, S. Olariu, Z. Wen
Computer Science Faculty Publications
An implementation of a double-ended priority queue is discussed. This data structure referred to as min–max–pair heap can be built in linear time; the operations Delete-min, Delete-max and Insert take O(log n) time, while Find-min and Find-max run in O(1) time. In contrast to the min-max heaps, it is shown that two min–max–pair heaps can be merged in sublinear time. More precisely, two min–max–pair heaps of sizes n and k can be merged in time O(log (n/k) * log k).
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 …