An implicit representation of chordal comparability graphs in linear time

作者：Curtis Andrew R; Izurieta Clemente; Joeris Benson; Lundberg Scott; McConnell Ross M^*

来源：Discrete Applied Mathematics, 2010, 158(8): 869-875.

DOI：10.1016/j.dam.2010.01.005

• Comparability graph
• Chordal graph
• Perfect graph
• Partial order
• Dimension

Ma and Spinrad have shown that every transitive orientation of a chordal comparability graph is the intersection of four linear orders. That is, chordal comparability graphs are comparability graphs of posers of dimension four Among other uses, this gives an implicit representation of a chordal comparability graph using O(n) integers so that, given two vertices, it can be determined in O(1) time whether they are adjacent, no matter how dense the graph is We give a linear time algorithm for finding the four linear orders, improving on their bound of O(n(2)).

• 出版日期2010-4-28