The minimum linear arrangement problem on proper interval graphs
arXiv:cs/0608008
Abstract
We present a linear time algorithm for the minimum linear arrangement problem on proper interval graphs. The obtained ordering is a 4-approximation for general interval graphs