d-dimensional arrangement revisited

DOI10.1016/J.IPL.2013.04.003MaRDI QIDQ2444745zbMATH OpenOpenAlexFDO

Authors Daniel Rotter, Jens Vygen

Publication date 11 April 2014

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.ipl.2013.04.003

zbMATH Keywords

\(d\)-dimensional arrangementapproximation algorithmsbalanced hierarchical decompositiongeometric embeddinggraph partitioninglinear arrangementspace-filling curve

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Approximation algorithms (68W25)

Recommendations

• A divide and conquer algorithm for d-dimensional arrangement
• Minimum \(d\)-dimensional arrangement with fixed points
• An improved approximation ratio for the minimum linear arrangement problem
• New Approximation Techniques for Some Linear Ordering Problems
• scientific article; zbMATH DE number 1303559

Cites work

• \(\ell ^2_2\) spreading metrics for vertex ordering problems
• \(O(\sqrt{\log n})\) approximation to sparsest cut in \(\tilde{O}(n^2)\) time
• A divide and conquer algorithm for d-dimensional arrangement
• A tight bound on approximating arbitrary metrics by tree metrics
• An improved approximation ratio for the minimum linear arrangement problem
• Divide-and-conquer approximation algorithms via spreading metrics
• Expander flows, geometric embeddings and graph partitioning
• Inapproximability Results for Maximum Edge Biclique, Minimum Linear Arrangement, and Sparsest Cut
• Integrality gaps for sparsest cut and minimum linear arrangement problems
• Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms
• New Approximation Techniques for Some Linear Ordering Problems
• Some simplified NP-complete graph problems
• Space-filling curves

Cited in

(3)

• A divide and conquer algorithm for d-dimensional arrangement
• Retracting Graphs to Cycles
• Minimum \(d\)-dimensional arrangement with fixed points

This page was built for publication: \(d\)-dimensional arrangement revisited

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