Lower bounds for the minimum linear arrangement of a graph

MaRDI QIDQ2861498zbMATH OpenFDO

Authors Alberto Caprara, Adam N. Letchford, Juan-José Salazar-González

Publication date 8 November 2013

Full work available at URL http://www.sciencedirect.com/science/article/pii/S1571065310001083

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Programming involving graphs or networks (90C35)

Recommendations

• Decorous lower bounds for minimum linear arrangement
• A New Lower Bound for the Minimum Linear Arrangement of a Graph
• Experiments on the minimum linear arrangement problem
• Optimal linear arrangements using betweenness variables
• Contributions to the minimum linear arrangement problem.

Cites work

• l²₂ spreading metrics for vertex ordering problems
• A Minimum Linear Arrangement Algorithm for Undirected Trees
• An effective two-stage simulated annealing algorithm for the minimum linear arrangement problem
• Approximating layout problems on random geometric graphs
• Divide-and-conquer approximation algorithms via spreading metrics
• Experiments on the minimum linear arrangement problem
• Flow metrics
• Generating lower bounds for the linear arrangement problem
• scientific article; zbMATH DE number 3700882 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1161294 (Why is no real title available?)
• Integrality gaps for sparsest cut and minimum linear arrangement problems
• Laying out sparse graphs with provably minimum bandwidth
• Optimal Assignments of Numbers to Vertices
• Optimal linear labelings and eigenvalues of graphs
• Optimal Numberings of an N \times N Array
• Planar linear arrangements of outerplanar graphs
• Some simplified NP-complete graph problems

Cited in

(19)

• New relationships for multi-neighborhood search for the minimum linear arrangement problem
• Optimal linear arrangements using betweenness variables
• Generating lower bounds for the linear arrangement problem
• An effective two-stage simulated annealing algorithm for the minimum linear arrangement problem
• Minimum linear arrangement of chord graphs
• Laying out sparse graphs with provably minimum bandwidth
• Decorous lower bounds for minimum linear arrangement
• Approximation Guarantees for the Minimum Linear Arrangement Problem by Higher Eigenvalues
• Minimum Linear Arrangement of Series-Parallel Graphs
• A New Lower Bound for the Minimum Linear Arrangement of a Graph
• scientific article; zbMATH DE number 4043771 (Why is no real title available?)
• Approximation guarantees for the minimum linear arrangement problem by higher eigenvalues
• Lower and upper bounds for the linear arrangement problem on interval graphs
• A note on minimum linear arrangement for BC graphs
• New Approximation Techniques for Some Linear Ordering Problems
• Minimum linear arrangement of the Cartesian product of optimal order graph and path
• scientific article; zbMATH DE number 6254006 (Why is no real title available?)
• Experiments on the minimum linear arrangement problem
• A mixed 0-1 linear programming formulation for the exact solution of the minimum linear arrangement problem

This page was built for publication: Lower bounds for the minimum linear arrangement of a graph

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2861498)