Quasimetric embeddings and their applications

DOI10.1007/s00453-018-0415-8zbMath1401.68255OpenAlexW2999389254MaRDI QIDQ1799224

Anastasios Sidiropoulos, Vijay Sridhar, Facundo Mémoli

Publication date: 18 October 2018

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2016/6200/

zbMATH Keywords

outlierstreewidthmetric embeddingsrandom embeddingsdirected multicutdirected sparsest-cutquasimetrics

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Planar graphs; geometric and topological aspects of graph theory (05C10)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Metric uniformization and spectral bounds for graphs
• An \(O(\sqrt n)\)-approximation algorithm for directed sparsest cut
• Extending Lipschitz functions via random metric partitions
• The geometry of graphs and some of its algorithmic applications
• Approximating directed multicuts
• On the hardness of approximating Multicut and Sparsest-Cut
• Measured descent: A new embedding method for finite metrics
• Hardness of cut problems in directed graphs
• Polynomial flow-cut gaps and hardness of directed cut problems
• Improved approximation for directed cut problems
• On the power of unique 2-prover 1-round games
• Directed metrics and directed graph partitioning problems
• Improved Approximation Algorithms for Minimum Weight Vertex Separators
• Approximation Algorithms for the 0-Extension Problem
• On the geometry of graphs with a forbidden minor
• Excluded minors, network decomposition, and multicommodity flow
• Randomly removing g handles at once
• Euclidean distortion and the sparsest cut
• Greedy approximation algorithms for directed multicuts
• The Unique Games Conjecture, Integrality Gap for Cut Problems and Embeddability of Negative-Type Metrics into ℓ ₁
• Expander flows, geometric embeddings and graph partitioning
• A tight bound on approximating arbitrary metrics by tree metrics

This page was built for publication: Quasimetric embeddings and their applications