Efficient Neighborhood Encoding for Interval Graphs and Permutation Graphs and O(n) Breadth-First Search

摘要

In this paper we address the problem of designing O(n) space representations for permutation and interval graphs that provide the neighborhood of any vertex in O(d) time, where d is its degree. To that purpose, we introduce a new parameter, called linearity, that would solve the problem if bounded for the two classes. Surprisingly, we show that it is not. Nevertheless, we design representations with the desired property for the two classes, and we implement the Breadth-First Search algorithm in O(n) time for permutation graphs; thereby lowering the complexity of All Pairs Shortest Paths and Single Source Shortest Path problems for the class.