Linear time algorithms to solve the linear ordering problem for oriented tree based graphs
RAIRO - Operations Research - Recherche Opérationnelle, Tome 50 (2016) no. 2, pp. 315-325.

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
Mots clés : 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://www.numdam.org/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://www.numdam.org/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://www.numdam.org/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, Tome 50 (2016) no. 2, pp. 315-325. doi : 10.1051/ro/2015024. http://www.numdam.org/articles/10.1051/ro/2015024/

S. Achouri, T. Bossart and A. Munier-Kordon, A polynomial algorithm for MINDSC on a subclass of serie parallel graphs. RAIRO: OR (2009) 145–156. | Numdam | MR | Zbl

D. Adolphson and T.C. Hu, Optimal Linear ordering. SIAM J. Appl. Math. 25 (1973) 403-423. | DOI | MR | Zbl

I. Charon and O. Hudry, An updated survey on the linear ordering problem for weighted or unweighted tournaments. Ann. Oper. Res. 175 (2010) 107–158. | DOI | MR | Zbl

F.R.K. Chung, On optimal linear arrangements of trees. Comput. Math. Appl. 10 (1984) 43–60. | DOI | MR | Zbl

J. Cohen, F. Fomin, P. Heggernes, D. Kratsch and G. Kucherov, Optimal Linear Arrangement of Interval Graphs, Proc. of MFCS’06 Proceedings of the 31st International Conference on Mathematical Foundations of Computer Science. Springer-Verlag, Berlin, Heidelberg (2006) 267–279. | MR | Zbl

D.G. Corneil, H. Kim, S. Natarajan, S. Olariu and A.P. Sprague, A simple linear time algorithm of unit interval graphs. Inf. Process. Lett. 55 (1995) 99–104. | DOI | MR | Zbl

S. Dasgupta, Ch. Papadimitriou and U.V. Vazirani, Algorithms. McGrawHill (2006).

J. Diaz, J. Petit and M. Serna, A survey of graph layout problems. J. ACM Comput. Surveys 349 (2002) 313–356. | DOI

M.R. Garey and D.S. Johnson, Computers and intractability: A guide to the theory of NP-Completeness. Computer Press (1979). | MR | Zbl

S.B. Horton, The optimal linear arrangement problem: algorithms ans approximation. Ph.D. thesis, Georgia Institute of Technology (1997).

W. Kubiak, D. Rebaine and C. Potts, HLF is optimal for scheduling a divide and conquer graph on m identical parallel machines. Discrete Optim. 6 (2009) 79–91. | DOI | MR | Zbl

V.J. Rayward-Smith and A.J. Clark, Scheduling theory applied to divide and conquer task systems on identical parallel machines, in Conpar’88, BCS Work shop Series. Edited by C.R. Jessehope, K.D. Reinartz. Cambridge University Press, Cambridge (1989).

J. Valdes, R.E. Tarjan and E.L. Lawler, The recognition of series parallel digraphs. SIAM J. Comput. 11 (1982) 298–317. | DOI | MR | Zbl

Cité par Sources :