Exact and Approximation Algorithms for Linear Arrangement Problems

• Autorzy: Alain Quiliot , Djamal Rebaine
• Języki publikacji: EN

Abstrakty

EN

We present here new results and algorithms for the Linear Arrangement Problem (LAP). We first propose a new lower bound, which links LAP with the Max Cut Problem, and derive a LIP model as well as a branch/bound algorithm for the general case. Then we focus on the case of interval graphs: we first show that our lower bound is tight for unit interval graphs, and derive an efficient polynomial time approximation algorithm for general interval graphs.(original abstract)

Słowa kluczowe

EN

Algorithms; Graphs; Mathematical analysis

PL

Algorytmy; Grafy; Analiza matematyczna

• Czasopismo: Annals of Computer Science and Information Systems
• Rocznik: 2014
• Tom: 2
• Strony: 493--500

Twórcy

autor

Alain Quiliot

• Université Blaise Pascal, France

autor

Djamal Rebaine

• l'Université du Québec à Montréal

Bibliografia

• Achouri S., Bossart T., Munier-Kordon A. (2009): A polynomial algorithm for MINDSC on a subclass of series parallel graphs, RAIRO Operations Research, pp. 145-156, DOI: 10.1051/ro/2009009
• Barahona F., Mahjoub A.R (1986): On the cut polytope, Math. Prog. 36, pp. 157-173, DOI: 10.1007/BF02592023
• Charon I., Hudry O. (2010): An updated survey on the linear ordering problem for weighted or unweighted tournaments, Annals of Operations Research, 175, pp. 107-158, DOI: 10.1007/010479-009-0648-7
• Chung FRK. (1984): On optimal linear arrangement of trees. Comp. & Maths/Appl., 11, pp. 43-60, DOI: 10.1145/73833.738333.73866
• Cohen J., Fomin F., Heggernes P., Kratsch D., Kucherov G. (2006): Optimal linear arrangement of interval graphs, Proc. MFCS'06, pp 267-279, Springer-Verlag, DOI: 10.1007/1182069_24
• Corneil DG., Kim H., Natarajan S., Olarin S., Sprague AP. (1995): A simple linear time algorithm of unit interval graphs, Information Processing Letters 55, pp. 99-104, DOI: 10.1016/0020-0190(95)00046-F
• Chvatal V., Ebenegger C. (1990): A note on line digraphs and the directed Max-Cut problem, Discrete Applied Maths 29, pp 165-170, DOI: 10.1016/0166-218X(90)90141-X
• Even S., Shiloach Y. (1975): NP-Completeness of Several Arrangement Problems, Technical Report