Irredundancy in Multiple Interval Representations.
Abstract
In a multiple interval intersection representation of a graph it is required that at least one interval from each of a pair of adjacent vertices intersect. It is permitted for there to be several such intersections even though these additional intersections are superfluous or redundant. By disallowing such redundancies one arrives at the concept of an irredundant multiple interval representation. This document shows that these irredundant representations can be much more inefficient than representations which allow redundancies. Finally, it is shown that even when some redundancy is permitted, the inefficiency remains. (Author)
Document Details
- Document Type
- Technical Report
- Publication Date
- Sep 01, 1984
- Accession Number
- ADA163310
Entities
People
- Edward R. Scheinerman
Organizations
- Johns Hopkins University