zbMATH — the first resource for mathematics

A new lower bound for the minimum linear arrangement of a graph. (English) Zbl 1341.05236
Liebling, Th. (ed.) et al., The IV Latin-American algorithms, graphs, and optimization symposium, Puerto Varas, Chile, November 25–29, 2007. Amsterdam: Elsevier. Electronic Notes in Discrete Mathematics 30, 87-92 (2008).
Summary: Given a graph \(G=(V,E)\) on \(n\) vertices, the minimum linear arrangement problem (MinLA) calls for a one-to-one function \(\psi : V \to \{1,\ldots, n\}\) which minimizes \(\sum_{\{i,j\}}E|\psi (i) - \psi (j)|\). MinLA is strongly NP-hard and very difficult to solve to optimality in practice. One of the reasons for this difficulty is the lack of good lower bounds. In this paper, we take a polyhedral approach to MinLA. We associate an integer polyhedron with each graph \(G\), and derive many classes of valid linear inequalities. It is shown that a cutting plane algorithm based on these inequalities can yield competitive lower bounds in a reasonable amount of time. A key to the success of our approach is that our linear programs contain only \(|E|\) variables. We conclude showing computational results on benchmark graphs from literature.
For the entire collection see [Zbl 1137.05001].

05C85 Graph algorithms (graph-theoretic aspects)
52B05 Combinatorial properties of polytopes and polyhedra (number of faces, shortest paths, etc.)
68Q25 Analysis of algorithms and problem complexity
Full Text: DOI
[1] Adolphson, D.; Hu, T.C., Optimal linear ordering, SIAM J. appl. math., 25, 403-423, (1973) · Zbl 0274.90061
[2] Bornstein, C.; Vempala, S., Flow metrics, Theor. comp. sci., 321, 13-24, (2004) · Zbl 1067.68177
[3] Díaz, J.; Petit, J.; Serna, M., A survey of graph layout problems, ACM computing surveys, 34, 313-356, (2002)
[4] Easton, T.; Horton, S.B.; Parker, R.G., A solvable case of the optimal linear arrangement problem on halin graphs, Congr. numer., 119, 3-17, (1996) · Zbl 0899.05058
[5] Even, G.; Naor, J.; Rao, S.; Schieber, B., Divide-and-conquer approximation algorithms via spreading metrics, J. of the ACM, 47, 585-616, (2000) · Zbl 1303.68156
[6] Feige, U.; Lee, J.R., An improved approximation ratio for the minimum linear arrangement problem, Inf. proc. lett., 101, 26-29, (2007) · Zbl 1185.68856
[7] Harper, L.H., Optimal assignment of numbers to vertices, SIAM journal, 12, 131-135, (1964) · Zbl 0222.94004
[8] Juvan, M.; Mohar, B., Optimal linear labellings and eigenvalues of graphs, Discr. appl. math., 36, 153-168, (1992) · Zbl 0759.05087
[9] Petit, J., Combining spectral sequencing and parallel simulated annealing for the minla problem, Parallel processing letters, 13, 77-91, (2003)
[10] Petit, J., Experiments on the linear arrangement problem, Journal of experimental algorithmics, 8, (2003), article 2.3 · Zbl 1069.90117
[11] Rao, S.; Richa, A.W., New approximation techniques for some linear ordering problems, SIAM J. on computing, 34, 388-404, (2005) · Zbl 1087.68130
[12] E. Rodriguez-Tello, J.-K. Hao & J. Torres-Jimenez (2007) An effective two-stage simulated annealing algorithm for the minimum linear arrangement problem. Comp. & Oper. Res., to appear · Zbl 1133.90424
[13] Safro, I.; Ron, D.; Brandt, A., Graph minimum linear arrangement by multilevel weighted edge contractions, J. of alg., 60, 24-41, (2006) · Zbl 1096.68687
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.