Geodesic
Lower and upper bounds for the linear arrangement problem on interval graphs
RAIRO - Operations Research - Recherche Opérationnelle, Tome 52 (2018) no. 4-5, pp. 1123-1145

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

We deal here with the Linear Arrangement Problem (LAP) on interval graphs, any interval graph being given here together with its representation as the intersection graph of some collection of intervals, and so with related precedence and inclusion relations. We first propose a lower bound LB, which happens to be tight in the case of unit interval graphs. Next, we introduce the restriction PCLAP of LAP which is obtained by requiring any feasible solution of LAP to be consistent with the precedence relation, and prove that PCLAP can be solved in polynomial time. Finally, we show both theoretically and experimentally that PCLAP solutions are a good approximation for LAP on interval graphs.

Reçu le :
Accepté le :
DOI : 10.1051/ro/2017011
Classification : 90C27
Keywords: Interval Graphs, Linear Ordering

Quilliot, Alain 1 ; Rebaine, Djamal 1 ; Toussaint, Hélène 1

1 
@article{RO_2018__52_4-5_1123_0,
     author = {Quilliot, Alain and Rebaine, Djamal and Toussaint, H\'el\`ene},
     title = {Lower and upper bounds for the linear arrangement problem on interval graphs},
     journal = {RAIRO - Operations Research - Recherche Op\'erationnelle},
     pages = {1123--1145},
     publisher = {EDP-Sciences},
     volume = {52},
     number = {4-5},
     year = {2018},
     doi = {10.1051/ro/2017011},
     mrnumber = {3878613},
     zbl = {1411.90299},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.1051/ro/2017011/}
}
TY  - JOUR
AU  - Quilliot, Alain
AU  - Rebaine, Djamal
AU  - Toussaint, Hélène
TI  - Lower and upper bounds for the linear arrangement problem on interval graphs
JO  - RAIRO - Operations Research - Recherche Opérationnelle
PY  - 2018
SP  - 1123
EP  - 1145
VL  - 52
IS  - 4-5
PB  - EDP-Sciences
UR  - http://geodesic.mathdoc.fr/articles/10.1051/ro/2017011/
DO  - 10.1051/ro/2017011
LA  - en
ID  - RO_2018__52_4-5_1123_0
ER  - 
%0 Journal Article
%A Quilliot, Alain
%A Rebaine, Djamal
%A Toussaint, Hélène
%T Lower and upper bounds for the linear arrangement problem on interval graphs
%J RAIRO - Operations Research - Recherche Opérationnelle
%D 2018
%P 1123-1145
%V 52
%N 4-5
%I EDP-Sciences
%U http://geodesic.mathdoc.fr/articles/10.1051/ro/2017011/
%R 10.1051/ro/2017011
%G en
%F RO_2018__52_4-5_1123_0
Quilliot, Alain; Rebaine, Djamal; Toussaint, Hélène. Lower and upper bounds for the linear arrangement problem on interval graphs. RAIRO - Operations Research - Recherche Opérationnelle, Tome 52 (2018) no. 4-5, pp. 1123-1145. doi: 10.1051/ro/2017011

Cité par Sources :