# Tag Info

2

It's an approximation algorithm, so the answer can be suboptimal. The answer of a given TSP is a Hamiltonian cycle, NOT Eulerian path. But the above doesn't justify that you have a wrong result, because simply: You forgot the last step, which is short-cutting -- removal of repeated vertices. So because you have two paths ($A \alpha B$ and $G \alpha H$) ...

2

Like other have pointed out, it seems you are confused by the difference between a minimum spanning tree, and a shortest path tree. A minimum spanning tree, is a tree such that it spans all vertices, and the sum of all edges is as minimum as possible. A shortest path tree, is a rooted tree such that the distance between the root, and any other vertex is as ...

1

What you are computing is typically called a shortest-path tree; yours is rooted at $a$. Note that, in this example, the shortest-path tree rooted at $a$ is not unique. You could have taken the edge $(d, e)$ instead of $(a, e)$.

1

The maximum spanning tree is about summing weights; maximizing the probability is about multiplying weights. To convert multiplication to sums, take the logarithm. Hopefully that's enough for you to work out an algorithm for this task.

1

You cannot show this since it isn't true. I encourage you to try out some actual numbers (e.g. $n=2$) and see for yourself that the numbers don't match. The problem is that what you should be subtracting is not the number of cycles of length $n-1$, but rather the number of collections of $n-1$ edges which contains at least one cycle. Such a collection need ...

1

I am not aware of any standard name for that kind of tree. One of the wonderful things about language is that we can describe things we don't already have a name for; there are many more interesting concepts than there are pre-existing widely-recognized names. I recommend that, if you find in your writing you need a concise name for it, you choose a name ...

1

The question and this post refers to this answer at its version 2. First of all, what does minimum disagreeing weight mean? The better word should have been "distinguishing". If the set of edges of some fixed weight in $T_1$ is different from that of $T_2$, then $T_1$ and $T_2$ disagree on that weight, i.e., that weight is distinguishing the two minimal ...

1

The maximum leaf spanning tree(MLSPT) is equivalent to the minimum connected dominating set(MCDS), see here. So we just need to prove MCDS is NP-complete. It's easy to verify that the decision version of MCDS is in NP. Similar to proof of NP completeness of dominating set, we perform a reduction from vertex cover(VC), i.e., we prove that $VC \le_p MCDS$: ...

1

I can find no requirement that all traffic is routed through the root switch. For example, in A<-->B<-->C, with C the root switch, traffic fom A to B does not pass through the root switch. The spanning tree protocol first selects a root switch. In Cisco, this is the switch with the lowest bridge ID. So the selection of the root is arbitrary. Now a ...

Only top voted, non community-wiki answers of a minimum length are eligible