Optimal Embedding into Star Metrics
From MaRDI portal
Publication:3183463
DOI10.1007/978-3-642-03367-4_26zbMath1253.68352OpenAlexW2153523737MaRDI QIDQ3183463
Publication date: 20 October 2009
Published in: Lecture Notes in Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-642-03367-4_26
Programming involving graphs or networks (90C35) Nonnumerical algorithms (68W05) Distance in graphs (05C12) Directed graphs (digraphs), tournaments (05C20)
Cites Work
- Minimum dilation stars
- Embedding into \(l_{\infty }^{2}\) is easy, embedding into \(l_{\infty}^{3}\) is NP-complete
- Computing a minimum-dilation spanning tree is NP-hard
- Parametric shortest path algorithms with an application to cyclic staffing
- A characterization of the minimum cycle mean in a digraph
- On a routing problem
- Towards a Genuinely Polynomial Algorithm for Linear Programming
- Computing Geometric Minimum-Dilation Graphs Is NP-Hard
- Applying Parallel Computation Algorithms in the Design of Serial Algorithms
- Combinatorial optimization with rational objective functions
- Metric spaces in pure and applied mathematics
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: Optimal Embedding into Star Metrics