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.
Accepté le :
DOI : 10.1051/ro/2015024
Mots-clés : Linear ordering, linear time algorithms, divide-and-conquer graphs, directed tree
@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://archive.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://archive.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://archive.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, 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. http://archive.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
and , Optimal Linear ordering. SIAM J. Appl. Math. 25 (1973) 403-423. | DOI | MR | Zbl
and , An updated survey on the linear ordering problem for weighted or unweighted tournaments. Ann. Oper. Res. 175 (2010) 107–158. | DOI | MR | Zbl
, 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
, , , and , 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).
, and , 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).
, and , HLF is optimal for scheduling a divide and conquer graph on 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).
, and , The recognition of series parallel digraphs. SIAM J. Comput. 11 (1982) 298–317. | DOI | MR | Zbl
Cité par Sources :
