A probabilistic algorithm for optimal linear arrangements

DOI10.1016/J.DAM.2026.05.001MaRDI QIDQ7289238zbMATH OpenFDO

Authors Daniel Berend, Shaked Mamana

Publication date 2 July 2026

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/J.DAM.2026.05.001

Mathematics Subject Classification ID

Distance in graphs (05C12) Graph theory (05C99)

Cites work

• A branch and bound algorithm for the matrix bandwidth minimization
• A correction on Shiloach's algorithm for minimum linear arrangement of trees
• A Remark on Stirling's Formula
• An improved approximation algorithm for dynamic minimum linear arrangement
• Assignment of Numbers to Vertices
• Branch and bound for the cutwidth minimization problem
• Complexity Results for Bandwidth Minimization
• Effect of initial assignment on local search performance for Max Sat
• Elevation of a graph
• Experiments on the minimum linear arrangement problem
• GRASP and path relinking for the matrix bandwidth minimization.
• scientific article; zbMATH DE number 3823859 (Why is no real title available?)
• scientific article; zbMATH DE number 4043771 (Why is no real title available?)
• scientific article; zbMATH DE number 4070955 (Why is no real title available?)
• scientific article; zbMATH DE number 176780 (Why is no real title available?)
• scientific article; zbMATH DE number 3526692 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1303526 (Why is no real title available?)
• scientific article; zbMATH DE number 1953102 (Why is no real title available?)
• On minimum cuts and the linear arrangement problem
• Optimal Assignments of Numbers to Vertices
• Optimal linear arrangement of a rectangular grid
• Optimal Linear Arrangement of Interval Graphs
• Optimal Linear Ordering
• Optimal Numberings of an N \times N Array
• Random graphs.
• Single Machine Job Sequencing with Precedence Constraints
• The itinerant list update problem
• The maximum linear arrangement problem for trees under projectivity and planarity
• The probabilistic method
• The sum of edge lengths in random linear arrangements
• Using the method of conditional expectations to supply an improved starting point for CCLS

This page was built for publication: A probabilistic algorithm for optimal linear arrangements

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