^2_2 spreading metrics for vertex ordering problems

DOI10.1007/S00453-008-9191-1zbMATH Open1194.68259OpenAlexW3004468478MaRDI QIDQ848848FDOQ848848

N. E. Zubov

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

Recommendations

• scientific article; zbMATH DE number 1303559
• Semi-definite relaxations for minimum bandwidth and other vertex-ordering problems
• New Approximation Techniques for Some Linear Ordering Problems
• Divide-and-conquer approximation algorithms via spreading metrics
• scientific article; zbMATH DE number 2086253

zbMATH Keywords

semidefinite programmingapproximation algorithmminimum linear arrangementminimum containing interval graphminimum storage-time productvertex ordering problem

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Semidefinite programming (90C22) Approximation algorithms (68W25) Distance in graphs (05C12)

Cites Work

• Applications of a Planar Separator Theorem
• The geometry of graphs and some of its algorithmic applications
• Measured descent: A new embedding method for finite metrics
• Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms
• Euclidean distortion and the sparsest cut
• An O(log k) Approximate Min-Cut Max-Flow Theorem and Approximation Algorithm
• Interior Point Methods in Semidefinite Programming with Applications to Combinatorial Optimization
• Expander flows, geometric embeddings and graph partitioning
• Approximating minimum feedback sets and multicuts in directed graphs
• O(√log n) approximation algorithms for min UnCut, min 2CNF deletion, and directed cut problems
• A framework for solving VLSI graph layout problems
• Embeddings of negative-type metrics and an improved approximation to generalized sparsest cut
• A unified approach to domination problems on interval graphs
• On Lipschitz embedding of finite metric spaces in Hilbert space
• On distance scales, embeddings, and efficient relaxations of the cut cone
• Fast Approximate Graph Partitioning Algorithms
• Approximation algorithms for low-distortion embeddings into low-dimensional spaces
• Divide-and-conquer approximation algorithms via spreading metrics
• Low-distortion embeddings of general metrics into the line
• Packing directed circuits fractionally
• Improved approximation algorithms for minimum-weight vertex separators
• Title not available (Why is that?)
• An improved approximation ratio for the minimum linear arrangement problem
• Title not available (Why is that?)
• Low-dimensional embedding with extra information
• Integrality gaps for sparsest cut and minimum linear arrangement problems

Cited In (10)

• Mildly Exponential Time Approximation Algorithms for Vertex Cover, Balanced Separator and Uniform Sparsest Cut
• \(d\)-dimensional arrangement revisited
• Distributed balanced partitioning via linear embedding
• Title not available (Why is that?)
• Flow metrics
• On a class of metrics related to graph layout problems
• Convex Relaxations for Permutation Problems
• Hardness and approximation of submodular minimum linear ordering problems
• New Approximation Techniques for Some Linear Ordering Problems
• Demand-aware network designs of bounded degree

This page was built for publication: \(\ell ^2_2\) spreading metrics for vertex ordering problems

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