Linear structure of bipartite permutation graphs and the longest path problem |
| |
Authors: | Ryuhei Uehara Gabriel Valiente |
| |
Affiliation: | a School of Information Science, JAIST, Ishikawa 923-1292, Japan b Department of Software, Technical University of Catalonia, E-08034 Barcelona, Spain |
| |
Abstract: | 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. |
| |
Keywords: | Bipartite permutation graphs Graph decomposition Linear time algorithms Graph algorithms |
本文献已被 ScienceDirect 等数据库收录! |
|