Approximation Guarantees for the Minimum Linear Arrangement Problem by Higher Eigenvalues

DOI10.1007/978-3-642-32512-0_27MaRDI QIDQ3167406zbMATH OpenOpenAlexFDO

Authors Suguru Tamaki, Yuichi Yoshida

Publication date 2 November 2012

Published in Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-32512-0_27

zbMATH Keywords

expander graphgraph LaplacianLasserre hierarchyordering problemsemidefinite programming

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Graph algorithms (graph-theoretic aspects) (05C85) Randomized algorithms (68W20) Approximation algorithms (68W25)

Recommendations

• Approximation guarantees for the minimum linear arrangement problem by higher eigenvalues
• An improved approximation ratio for the minimum linear arrangement problem
• scientific article; zbMATH DE number 1617262
• Approximation algorithms for maximum linear arrangement
• A compact quadratic model and linearizations for the minimum linear arrangement problem
• Tractable parameterizations for the minimum linear arrangement problem
• Tractable parameterizations for the minimum linear arrangement problem
• Lower bounds for the minimum linear arrangement of a graph
• Decorous lower bounds for minimum linear arrangement
• Approximating Minimum Linear Ordering Problems

Cited in

(3)

• Approximation guarantees for the minimum linear arrangement problem by higher eigenvalues
• Ordering a Sparse Graph to Minimize the Sum of Right Ends of Edges
• An improved approximation ratio for the minimum linear arrangement problem

This page was built for publication: Approximation Guarantees for the Minimum Linear Arrangement Problem by Higher Eigenvalues

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