All geek questions in one place

Jam when solving the minimum pairing problem

I reduced my problem to finding the minimum spanning tree in the graph. But I want to have one more limitation, which is that the total degree for each vertex should not exceed a certain constant coefficient. How to simulate my problem? Is MST the wrong way? Do you know any algorithms that will help me?

Another problem: my graph has repeated edge weights, so is there a way to count the number of unique MSTs? Are there algorithms that do this?

Thanks.

Edit: by degree, I mean the total number of edges connecting the vertex. By double the weight of the edge, I mean that two edges have the same weight.

+3
source share
3 answers

This article shows how to find in polynomial time a spanning tree of maximum degree d + 1, which is at least as good as any spanning tree of maximum degree d: http://www.andrew.cmu.edu/user/ mohits / mbdst.pdf

// Edit The original link is currently inactive, try http://research.microsoft.com/pubs/80193/mbdst.pdf instead .

+1
source

Well, it's easy to prove that there might not be a solution: just make your input graph a tree with a vertex with a degree higher than your limit.

+2
source

For Gary Johnson, this problem boiled down to Hamilton: (It helped. Approximating the first: http://caislab.icu.ac.kr/Lecture/data/2003/spring/ice514/project/m03.ppt However, the best working models are rated .. .

Counting: http://mathworld.wolfram.com/SpanningTree.html . In accordance with this, mathematics has a function. Any suggestions on this?

+2
source

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

More articles:


All Articles