All geek questions in one place

Algorithm for a minimum spanning tree with a limited degree + limited diameter?

Suppose I have 3 kinds of constraints for calculating a spanning tree:

  • Limited degree (for example: a node in a spanning tree can connect up to 3 other nodes)
  • A limited diameter (for example, all ribs) of the weight, once summed, cannot exceed 100).
    2.1. If possible, show all subtrees matching these criteria.
  • AND

Are there any good algorithms to solve this problem that will not infuriate me? I need to run this with fairly large capabilities (1000+ nodes), so its complexity also cannot be too high.

+3
source share
1 answer

The spanning tree problem with a limited degree of complexity is NP-complete. See http://en.wikipedia.org/wiki/Degree-constrained_spanning_tree . So, no good (i.e. polynomial) algorithms. However, there are approximation algorithms.

A Google search seems to indicate that the problem of binding with a limited diameter is equally complex.

+2
source

Source: https://habr.com/ru/post/1756670/

More articles:


All Articles