The Minimum Linear Arrangement Problem on Bipartite Г-oriented Graphs - Rafayelyan, Levon R. (Mathematical Problems of Computer Science, 2021)
In general case the minimum linear arrangement (MINLA) problem is NP-complete. It is NP-complete also for bipartite graphs. In this paper it is proved that a minimum linear arrangement for bipartite ¡-oriented graphs can be found in polynomial time. The formula for the cost of optimal arrangement is given as well.