This question is motivated by the task of "uniformly" bicoloring the vertices of a symmetric TSP-instance graph with $2n$ vertices.

A simple heuristical requirement for such a bicoloring could be that for each vertex one of the nearby neighbors should be colored differently.

Using the edges of a minimum weight perfect matching is the obvious solution for pairing up "nearby" vertices and then augmenting that set of edges to a connected, bipartite graph via Kruskal's MST algorithm, however starting with the matching's edges as initial connected components.

The bicoloring can then obtained by bicoloring the vertices of that spanning tree.

The images below depict 50 resp. 500 bicolored points using euclidean distance as the measure of proximity.

Bicoloring 50 Random Points
Bicoloring 500 Random Points

As the idea of augmenting a perfect matching to a spanning tree isn't very elaborate, I suspect that those kinds of spanning trees have already been encountered.


is there an established name for spanning trees obtained by Kruskal's algorithm starting from the edges of a minimum weight perfect matching as the initial connected components?


Your Answer

By clicking "Post Your Answer", you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.