Carregant...
Carregant...

Vés al contingut (premeu Retorn)

Linear structure of bipartite permutation graphs and the longest path problem

Autor
Uehara, R.; Valiente, G.
Tipus d'activitat
Article en revista
Revista
Information processing letters
Data de publicació
2007-07-16
Volum
103
Número
2
Pàgina inicial
71
Pàgina final
77
DOI
https://doi.org/10.1016/j.ipl.2007.02.010 Obrir en finestra nova
URL
http://www.sciencedirect.com/science/article/pii/S0020019007000464 Obrir en finestra nova
Resum
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...
Paraules clau
Bipartite permutation graphs, Graph algorithms, Graph decomposition, Linear time algorithms
Grup de recerca
ALBCOM - Algorismia, Bioinformàtica, Complexitat i Mètodes Formals

Participants