| Issue |
RAIRO-Oper. Res.
Volume 50, Number 2, April-June 2016
Special issue: Research on Optimization and Graph Theory dedicated to COSI 2013
|
|
|---|---|---|
| Page(s) | 315 - 325 | |
| DOI | https://doi.org/10.1051/ro/2015024 | |
| Published online | 21 March 2016 | |
Linear time algorithms to solve the linear ordering problem for oriented tree based graphs
1 Université Blaise Pascal, LIMOS, UMR CNRS 6158, BP 10125
Campus des Cézeaux, 63173 Aubière, France.
alain.quilliot@isima.fr
2 Université du Québec à Chicoutimi, Département d’informatique
et mathématique, 555, Bld. de l’Université, Saguenay, Québec, Canada.
djamalrebaine@uqac.ca
Received:
18
May
2015
Accepted:
1
June
2015
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.
Mathematics Subject Classification: 9008
Key words: Linear ordering / linear time algorithms / divide-and-conquer graphs / directed tree
© EDP Sciences, ROADEF, SMAI 2016
Current usage metrics show cumulative count of Article Views (full-text article views including HTML views, PDF and ePub downloads, according to the available data) and Abstracts Views on Vision4Press platform.
Data correspond to usage on the plateform after 2015. The current usage metrics is available 48-96 hours after online publication and is updated daily on week days.
Initial download of the metrics may take a while.