2012/06/30 by Sven Herrmann, Vincent Moulton, Andreas Spillner · 2 citations
Biochemistry, Genetics and Molecular Biology · Computer Science · Mathematics · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Edge contraction #Finite set #Graph #Heuristic #Metric (unit) #Metric space #Representation (politics) #Simplex #Topological and Geometric Data Analysis #math.CO #math.MG #msc:05C05 #msc:51K05 #msc:52B55 #msc:92D15 #q-bio.QM
paper · pdf · doi:10.1016/j.disopt.2013.08.002
published in Discrete Optimization 10(4), 310-319 (Elsevier BV) · 20 pages, 3 figures
openalex publication_date 2013/09/18 · arxiv created 2014/12/22 · arxiv updated 2014/12/23 · openalex created_date 2016/06/24 · openalex updated_date 2026/08/05
An important problem that commonly arises in areas such as internet traffic-flow analysis, phylogenetics and electrical circuit design, is to find a representation of any given metric D on a finite set by an edge-weighted graph, such that the total edge length of the graph is minimum over all such graphs. Such a graph is called an optimal realization and finding such realizations is known to be NP-hard. Recently Varone presented a heuristic greedy algorithm for computing optimal realizations. Here we present an alternative heuristic that exploits the relationship between realizations of the metric D and its so-called tight span TD. The tight span TD is a canonical polytopal complex that can be associated to D, and our approach explores parts of TD for realizations in a way that is similar to the classical simplex algorithm. We also provide computational results illustrating the performance of our approach for different types of metrics, including l1-distances and two-decomposable metrics for which it is provably possible to find optimal realizations in their tight spans.