Graph Theory: What is the definition of the "Sorted Edge" algorithm?
By John Peck •
I've been googling for a while and can't find a clear definition of the "sorted edge" algorithm--can anyone provide it please?
A description would be helpful, but a simple statement of the algorithm may be sufficient.
Thank you.
$\endgroup$1 Answer
$\begingroup$The algorithm sorts the edges in ascending order by cost. You choose edges in greedy order to create a path. So no three edges are incident to the same vertex, and you don't close the path to a circuit unless it is a Hamiltonian path.
This looks like a heuristic to solve the traveling salesman problem based on Kruskal's algorithm.
$\endgroup$
