Lower and upper bounds for the linear arrangement problem on interval graphs
Alain Quilliot, Djamal Rebaïne, Hélène Toussaint · RAIRO - Operations Research · 2017
We deal here with theLinear Arrangement Problem(LAP) onintervalgraphs, any interval graph being given here together with its representation as theintersectiongraph of some collection of intervals, and so with relatedprecedenceandinclusionrelations. We first propose a lower boundLB, which happens to be tight in the case ofunit intervalgraphs. Next, we introduce the restriction PCLAP of LAP which is obtained by requiring any feasible solution of LAP to be consistent with theprecedencerelation, 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 onintervalgraphs.