Optimizations for building path

rivetTDA / rivet

RIVET is a tool for Topological Data Analysis, in particular two-parameter persistent homology.

GNU General Public License v3.0

73 stars 24 forks source link

Optimizations for building path #15

Open mlesnick opened 9 years ago

mlesnick commented 9 years ago

Originally reported by: Matthew Wright (GitHub: mlwright84)

Implement edge-weighting algorithm
From the minimal spanning tree, choose a path that minimizes backgracking
Christofides' 3/2 approximation for the path through the dual graph.

mlesnick commented 7 years ago

Original comment by M L (GitHub: mlesnick):

could make RIVET faster, but not a major priority at the moment, since other pending improvements are expected to make a much bigger difference in terms of efficiency.

mlesnick commented 8 years ago

Original comment by Matthew Wright (GitHub: mlwright84):

Our edge-weighting algorithm is implemented, but our path can still be improved. The current implementation does not minimize backtracking in the MST, and also doesn't use the variant of Christofides' algorithm mentioned in our paper.