Linear structure of bipartite permutation graphs and the longest path problem

详细信息    查看全文

• 作者：Ryuhei Uehara ; Gabriel Valiente
• 关键词：Bipartite permutation graphs ; Graph decomposition ; Linear time algorithms ; Graph algorithms
• 刊名：Information Processing Letters
• 出版年：2007
• 出版时间：16 July 2007
• 年：2007
• 卷：103
• 期：2
• 页码：71-77
• 全文大小：250 K

文摘

The class of bipartite permutation graphs is the intersection of two well known graph classes: bipartite graphs and permutation graphs. A complete bipartite decomposition of a bipartite permutation graph is proposed in this note. The decomposition gives a linear structure of bipartite permutation graphs, and it can be obtained in O(n) time, where n is the number of vertices. As an application of the decomposition, we show an O(n) time and space algorithm for finding a longest path in a bipartite permutation graph.