\(\ell ^2_2\) spreading metrics for vertex ordering problems
From MaRDI portal
Publication:848848
DOI10.1007/s00453-008-9191-1zbMath1194.68259OpenAlexW3004468478MaRDI QIDQ848848
Publication date: 23 February 2010
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00453-008-9191-1
semidefinite programmingapproximation algorithmminimum linear arrangementminimum containing interval graphminimum storage-time productvertex ordering problem
Semidefinite programming (90C22) Graph theory (including graph drawing) in computer science (68R10) Distance in graphs (05C12) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)
Related Items (6)
Convex Relaxations for Permutation Problems ⋮ On a class of metrics related to graph layout problems ⋮ Demand-aware network designs of bounded degree ⋮ \(d\)-dimensional arrangement revisited ⋮ Mildly Exponential Time Approximation Algorithms for Vertex Cover, Balanced Separator and Uniform Sparsest Cut ⋮ Distributed balanced partitioning via linear embedding
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A framework for solving VLSI graph layout problems
- An improved approximation ratio for the minimum linear arrangement problem
- On Lipschitz embedding of finite metric spaces in Hilbert space
- A unified approach to domination problems on interval graphs
- Approximating minimum feedback sets and multicuts in directed graphs
- The geometry of graphs and some of its algorithmic applications
- Packing directed circuits fractionally
- Measured descent: A new embedding method for finite metrics
- Integrality gaps for sparsest cut and minimum linear arrangement problems
- Divide-and-conquer approximation algorithms via spreading metrics
- Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms
- Low-distortion embeddings of general metrics into the line
- Euclidean distortion and the sparsest cut
- Improved approximation algorithms for minimum-weight vertex separators
- O(√log n) approximation algorithms for min UnCut, min 2CNF deletion, and directed cut problems
- Applications of a Planar Separator Theorem
- Fast Approximate Graph Partitioning Algorithms
- An O(log k) Approximate Min-Cut Max-Flow Theorem and Approximation Algorithm
- Interior Point Methods in Semidefinite Programming with Applications to Combinatorial Optimization
- Low-dimensional embedding with extra information
- Expander flows, geometric embeddings and graph partitioning
This page was built for publication: \(\ell ^2_2\) spreading metrics for vertex ordering problems
