BazEkon - The Main Library of the Cracow University of Economics

BazEkon home page

Main menu

Quiliot Alain (Université Blaise Pascal, France), Rebaine Djamal (l'Université du Québec à Montréal)
Exact and Approximation Algorithms for Linear Arrangement Problems
Annals of Computer Science and Information Systems, 2014, vol. 2, s. 493 - 500, rys., tab., bibliogr. 11 poz.
Algorytmy, Grafy, Analiza matematyczna
Algorithms, Graphs, Mathematical analysis
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)
Full text
  1. 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
  2. Barahona F., Mahjoub A.R (1986): On the cut polytope, Math. Prog. 36, pp. 157-173, DOI: 10.1007/BF02592023
  3. 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
  4. Chung FRK. (1984): On optimal linear arrangement of trees. Comp. & Maths/Appl., 11, pp. 43-60, DOI: 10.1145/73833.738333.73866
  5. 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
  6. 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
  7. 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
  8. Even S., Shiloach Y. (1975): NP-Completeness of Several Arrangement Problems, Technical Report #43, Computer Science Department, The Technion, Haifa, Israel, DOI: 10.1007/11821069_24
  9. Garey MR., Johnson DS. (1979): Computers and intractability: a guide to the theory of NP-completeness, Computer Press, ISBN-13: 978-0716710455.
  10. Grotschel, M. (ed.) (2004): The Sharpest Cut, MPSSIAM Series on Optimization, ISBN-13: 978-0898715521
  11. Horton SB. (1997): The optimal linear arrangement problem: algorithms and approximation, Phd thesis, Georgia Institute of Technology
Cited by
Share on Facebook Share on Twitter Share on Google+ Share on Pinterest Share on LinkedIn Wyślij znajomemu