Optimal Embedding into Star Metrics

DOI10.1007/978-3-642-03367-4_26zbMath1253.68352OpenAlexW2153523737MaRDI QIDQ3183463

Kevin Wortman, David Eppstein

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

Mathematics Subject Classification ID

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