LINEAR TIME ALGORITHMS TO SOLVE THE LINEAR ORDERING PROBLEM FOR ORIENTED TREE BASED GRAPHS

被引：2

作者：

Quilliot, Alain ^{[1
]}

Rebaine, Djamal ^{[2
]}

机构：

[1] Univ Blaise Pascal, LIMOS, UMR CNRS 6158, BP 10125 Campus Cezeaux, F-63173 Aubiere, France

[2] Univ Quebec Chicoutimi, Dept Math & Informat, 555 Bld Univ, Saguenay, PQ, Canada

来源：

RAIRO-OPERATIONS RESEARCH | 2016年 / 50卷 / 02期

基金：

加拿大自然科学与工程研究理事会;

关键词：

Linear ordering; linear time algorithms; divide-and-conquer graphs; directed tree; RECOGNITION;

D O I：

10.1051/ro/2015024

中图分类号：

C93 [管理学]; O22 [运筹学];

学科分类号：

070105 ; 12 ; 1201 ; 1202 ; 120202 ;

摘要：

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.

引用

页码：315 / 325

页数：11

共 13 条

[1] A POLYNOMIAL ALGORITHM FOR MINDSC ON A SUBCLASS OF SERIES PARALLEL GRAPHS
Achouri, Salim
Bossart, Timothee
Munier-Kordon, Alix
[J]. RAIRO-OPERATIONS RESEARCH, 2009, 43 (02) : 145 - 156
[2] OPTIMAL LINEAR ORDERING
ADOLPHSON, D
HU, TC
[J]. SIAM JOURNAL ON APPLIED MATHEMATICS, 1973, 25 (03) : 403 - 423
[3] [Anonymous], 1979, Computers and Intractablity: A Guide to the Theory of NP-Completeness
[4] An updated survey on the linear ordering problem for weighted or unweighted tournaments
Charon, Irene
Hudry, Olivier
[J]. ANNALS OF OPERATIONS RESEARCH, 2010, 175 (01) : 107 - 158
[5] ON OPTIMAL LINEAR ARRANGEMENTS OF TREES
CHUNG, FRK
[J]. COMPUTERS & MATHEMATICS WITH APPLICATIONS, 1984, 10 (01) : 43 - 60
[6] Cohen J, 2006, LECT NOTES COMPUT SC, V4162, P267
[7] SIMPLE LINEAR-TIME RECOGNITION OF UNIT INTERVAL-GRAPHS
CORNEIL, DG
KIM, HY
NATARAJAN, S
OLARIU, S
SPRAGUE, AP
[J]. INFORMATION PROCESSING LETTERS, 1995, 55 (02) : 99 - 104
[8] Dasgupta S., 2006, ALGORITHMS
[9] A survey of graph layout problems
Díaz, J
Petit, J
Serna, M
[J]. ACM COMPUTING SURVEYS, 2002, 34 (03) : 313 - 356
[10] Horton S.B., 1997, THESIS

← 1 2 →