Decorous Lower Bounds for Minimum Linear Arrangement

References

• Amaral A. R. S., Letchford A. N. A polyhedral approach to the single row facility layout problem. (2006) . Working paper, Lancaster University, Lancaster, UKGoogle Scholar
• Ambühl C., Mastrolilli M., Svensson O. Inapproximability results for sparsest cut, optimal linear arrangement, and precedence constrained scheduling. Proc. 48th Annual IEEE Sympos. Foundations Comput. Sci. (2007) (IEEE Computer Society Press, Los Alamitos, CA) 329–337Crossref, Google Scholar
• Bornstein C. F., Vempala S. Flow metrics. Theoret. Comput. Sci. (2004) 321(1):13–24Crossref, Google Scholar
• Caprara A., Salazar-González J. J. Laying out sparse graphs with provably minimum bandwidth. INFORMS J. Comput. (2005) 17(3):356–373Link, Google Scholar
• Caprara A., Jung M., Oswald M., Reinelt G., Traversi E. A betweenness approach for solving the linear arrangement problem. (2009) . Working paper, DEIS, Università di Bologna, Bologna, ItalyGoogle Scholar
• Charikar M., Hajiaghayi M. T., Karloff H., Rao S. l22 spreading metrics for vertex ordering problems. Algorithmica (2010) 56(4):577–604Crossref, Google Scholar
• Chung F. R. K., Beineke L., Wilson R. Labellings of graphs. Selected Topics in Graph Theory 3 (1988) (Academic Press, San Diego) 151–168Google Scholar
• Devanur N. R., Khot S. A., Saket R., Vishnoi N. K. On the hardness of minimum linear arrangement. (2006) . Working paper, Georgia Institute of Technology, AtlantaGoogle Scholar
• Díaz J., Petit J., Serna M. A survey of graph layout problems. ACM Comput. Surveys (2002) 34(3):313–356Crossref, Google Scholar
• Easton T., Horton S. B., Parker R. G. A solvable case of the optimal linear arrangement problem on Halin graphs. Congressus Numerantium (1996) 119:3–17Google Scholar
• Even G., Naor J. S., Rao S., Schieber B. Divide-and-conquer approximation algorithms via spreading metrics. J. ACM (2000) 47(4):585–616Crossref, Google Scholar
• Feige U., Lee J. R. An improved approximation ratio for the minimum linear arrangement problem. Inform. Processing Lett. (2007) 101(1):26–29Crossref, Google Scholar
• Frederickson G. N., Hambrush S. E. Planar linear arrangements of outerplanar graphs. IEEE Trans. Circuits Systems (1988) 35(3):323–332Crossref, Google Scholar
• Garey M. R., Johnson D. S.Computers and Intractability: An Introduction to the Theory of 𝒩𝒫-Completeness (1979) (Freeman, New York) Google Scholar
• Garey M. R., Johnson D. S., Stockmeyer L. J. Some simplified 𝒩𝒫-complete graph problems. Theoret. Comput. Sci. (1976) 1(3):237–267Crossref, Google Scholar
• Grötschel M., Lovász L., Schrijver A. J.Geometric Algorithms and Combinatorial Optimization (1988) (John Wiley & Sons, New York) Crossref, Google Scholar
• Harper L. H. Optimal assignments of numbers to vertices. SIAM J. Appl. Math. (1964) 12(1):131–135Crossref, Google Scholar
• Juvan M., Mohar B. Optimal linear labelings and eigenvalues of graphs. Discrete Appl. Math. (1992) 36(2):153–168Crossref, Google Scholar
• Koren Y., Harel D., Kučera L. A multi-scale algorithm for the linear arrangement problem. Proc. 28th Internat. Workshop Graph-Theoretic Concepts in Comput. Sci. (2002) 2573(Springer, Berlin) 293–306Lecture Notes in Computer ScienceCrossref, Google Scholar
• Liu W., Vannelli A. Generating lower bounds for the linear arrangement problem. Discrete Appl. Math. (1995) 59(2):137–151Crossref, Google Scholar
• Mitchison G., Durbin R. Optimal numberings of an n × n array. SIAM J. Discrete Math. (1986) 7(4):571–582Crossref, Google Scholar
• Nemhauser G. L., Wolsey L. A.Integer and Combinatorial Optimization (1988) (Wiley, Chichester, UK) Crossref, Google Scholar
• Muradyan D. O., Piliposjan T. E. Minimal numberings of vertices of a rectangular lattice. Akademii Nauk Armianskoi SSR (in Russian) (1980) 1(70):21–27Google Scholar
• Petit J. Layout problems. (2001) . Ph.D. thesis, Department of Languages and Information Systems, Universitat Politècnica de Catalunya, Barcelona, SpainGoogle Scholar
• Petit J. Combining spectral sequencing and parallel simulated annealing for the MinLA problem. Parallel Processing Lett. (2003a) 13(1):77–91Crossref, Google Scholar
• Petit J. Experiments on the linear arrangement problem. J. Experiment. Algorithmics (2003b) 8Article 2.3Crossref, Google Scholar
• Rao S., Richa A. W. New approximation techniques for some linear ordering problems. SIAM J. Comput. (2005) 34(2):388–404Crossref, Google Scholar
• Reinelt G. (2009) . Personal communicationGoogle Scholar
• Rodriguez-Tello E., Hao J.-K., Torres-Jimenez J. An effective two-stage simulated annealing algorithm for the minimum linear arrangement problem. Comput. Oper. Res. (2008) 35(10):3331–3346Crossref, Google Scholar
• Safro I., Ron D., Brandt A. Graph minimum linear arrangement by multilevel weighted edge contractions. J. Algorithms (2006) 60(1):24–41Crossref, Google Scholar
• Shiloach Y. A minimum linear arrangement algorithm for undirected trees. SIAM J. Comput. (1979) 8(1):15–32Crossref, Google Scholar