An improved approximation ratio for the minimum linear arrangement problem
From MaRDI portal
Publication:845884
DOI10.1016/j.ipl.2006.07.009zbMath1185.68856OpenAlexW2007525305MaRDI QIDQ845884
Publication date: 29 January 2010
Published in: Information Processing Letters (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.ipl.2006.07.009
Related Items
Ordering a Sparse Graph to Minimize the Sum of Right Ends of Edges ⋮ Minimum Linear Arrangement of Series-Parallel Graphs ⋮ Convex Relaxations for Permutation Problems ⋮ \(\ell ^2_2\) spreading metrics for vertex ordering problems ⋮ Bounds on the Geometric Mean of Arc Lengths for Bounded-Degree Planar Graphs ⋮ On a class of metrics related to graph layout problems ⋮ Demand-aware network designs of bounded degree ⋮ A New Lower Bound for the Minimum Linear Arrangement of a Graph ⋮ \(d\)-dimensional arrangement revisited ⋮ Mildly Exponential Time Approximation Algorithms for Vertex Cover, Balanced Separator and Uniform Sparsest Cut ⋮ Distributed balanced partitioning via linear embedding ⋮ Low-light trees, and tight lower bounds for Euclidean spanners ⋮ On an ordering problem in weighted hypergraphs
Cites Work
- Unnamed Item
- Unnamed Item
- Divide-and-conquer approximation algorithms via spreading metrics
- Euclidean distortion and the sparsest cut
- l22 spreading metrics for vertex ordering problems
- New Approximation Techniques for Some Linear Ordering Problems
- Excluded minors, network decomposition, and multicommodity flow
- Expander flows, geometric embeddings and graph partitioning