The Minimum Linear Arrangement Problem on Bipartite Г-oriented Graphs

Authors

  • Levon R. Rafayelyan Yerevan State University

Abstract

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.

References

M.R. Garey, D.S. Johnson, Computers and Intractability. A guide to the theory of NP-completeness. Freeman and Company, 1979.

S. Even, Y. Shiloah, NP-completeness of several arrangement problems, Report No. 43, Dept. of Computer Science, Technion, Haifa, Israel, 1975.

Downloads

Published

2021-12-10

How to Cite

Rafayelyan, L. R. . (2021). The Minimum Linear Arrangement Problem on Bipartite Г-oriented Graphs. Mathematical Problems of Computer Science, 32, 23–26. Retrieved from http://mpcs.sci.am/index.php/mpcs/article/view/356

Issue

Vol. 32 (2009): Mathematical Problems of Computer Science

Section

Articles

License

Creative Commons License

This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.