1
$\begingroup$

Let the edge set of a Optimal k-Tour Spanner of a graph $G$ be equal to the edges of $G$ that lie on at least one optimal tour through exactly $3<k<n$ distinct vertices of $G$.

I would like to know, whether such spanners have already been investigated and, specifically:

  • do such spanners contain the shortest tour through all vertices of $G$?

  • for which kind of complete graphs $G$ is the Optimal k-Tour Spanner also a complete graph for every $3<k<n$ (if a planar pointset is in strictly convex configuration, then the derived distance graph has that property)?

$\endgroup$

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.