Geodesic
Linear time algorithms to solve the linear ordering problem for oriented tree based graphs
Quilliot, Alain1  ; Rebaine, Djamal2
1 Université Blaise Pascal, LIMOS, UMR CNRS 6158, BP 10125 Campus des Cézeaux, 63173 Aubière, France.
2 Université du Québec à Chicoutimi, Département d’informatique et mathématique, 555, Bld. de l’Université, Saguenay, Québec, Canada.
RAIRO - Operations Research - Recherche Opérationnelle, Special issue: Research on Optimization and Graph Theory dedicated to COSI 2013 / Special issue: Recent Advances in Operations Research in Computational Biology, Bioinformatics and Medicine, Tome 50 (2016) no. 2, pp. 315-325

Voir la notice de l'article provenant de la source Numdam

We present in this paper two simple linear algorithms that solve to optimality the linear ordering problem for unweighted tree based graphs viz. the oriented trees and the oriented divide-and-conquer graphs.

Reçu le :
Accepté le :
DOI : 10.1051/ro/2015024
Classification : 9008
Keywords: Linear ordering, linear time algorithms, divide-and-conquer graphs, directed tree

Quilliot, Alain 1 ; Rebaine, Djamal 2

1 Université Blaise Pascal, LIMOS, UMR CNRS 6158, BP 10125 Campus des Cézeaux, 63173 Aubière, France.
2 Université du Québec à Chicoutimi, Département d’informatique et mathématique, 555, Bld. de l’Université, Saguenay, Québec, Canada. 
@article{RO_2016__50_2_315_0,
     author = {Quilliot, Alain and Rebaine, Djamal},
     title = {Linear time algorithms to solve the linear ordering problem for oriented tree based graphs},
     journal = {RAIRO - Operations Research - Recherche Op\'erationnelle},
     pages = {315--325},
     publisher = {EDP-Sciences},
     volume = {50},
     number = {2},
     year = {2016},
     doi = {10.1051/ro/2015024},
     mrnumber = {3479871},
     zbl = {1338.90254},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.1051/ro/2015024/}
}
TY  - JOUR
AU  - Quilliot, Alain
AU  - Rebaine, Djamal
TI  - Linear time algorithms to solve the linear ordering problem for oriented tree based graphs
JO  - RAIRO - Operations Research - Recherche Opérationnelle
PY  - 2016
SP  - 315
EP  - 325
VL  - 50
IS  - 2
PB  - EDP-Sciences
UR  - http://geodesic.mathdoc.fr/articles/10.1051/ro/2015024/
DO  - 10.1051/ro/2015024
LA  - en
ID  - RO_2016__50_2_315_0
ER  - 
%0 Journal Article
%A Quilliot, Alain
%A Rebaine, Djamal
%T Linear time algorithms to solve the linear ordering problem for oriented tree based graphs
%J RAIRO - Operations Research - Recherche Opérationnelle
%D 2016
%P 315-325
%V 50
%N 2
%I EDP-Sciences
%U http://geodesic.mathdoc.fr/articles/10.1051/ro/2015024/
%R 10.1051/ro/2015024
%G en
%F RO_2016__50_2_315_0
Quilliot, Alain; Rebaine, Djamal. Linear time algorithms to solve the linear ordering problem for oriented tree based graphs. RAIRO - Operations Research - Recherche Opérationnelle, Special issue: Research on Optimization and Graph Theory dedicated to COSI 2013 / Special issue: Recent Advances in Operations Research in Computational Biology, Bioinformatics and Medicine, Tome 50 (2016) no. 2, pp. 315-325. doi: 10.1051/ro/2015024

Cité par Sources :