BazEkon - Biblioteka Główna Uniwersytetu Ekonomicznego w Krakowie

BazEkon home page

Meny główne

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.
Słowa kluczowe
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)
Pełny tekst
  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
Cytowane przez
Udostępnij na Facebooku Udostępnij na Twitterze Udostępnij na Google+ Udostępnij na Pinterest Udostępnij na LinkedIn Wyślij znajomemu