Quasimetric embeddings and their applications
From MaRDI portal
Publication:1799224
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/
outlierstreewidthmetric embeddingsrandom embeddingsdirected multicutdirected sparsest-cutquasimetrics
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 ℓ 1
- 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
