Quantum Verification of Minimum Spanning Tree

Details Quantum Verification of Minimum Spanning Tree Quantum Verification of Minimum Spanning Tree

2011-12-05

arxiv.org/abs/1112.1139v1

Physics

Quantum Physics

5 papges

Scientific paper

Previous studies has shown that for a weighted undirected graph having $n$ vertices and $m$ edges, a minimal weight spanning tree can be found with $O^*(\sqrt{mn})$ calls to the weight oracle. The present note shows that a given spanning tree can be verified to be a minimal weight spanning tree with only $O(n\bigr)$ calls to the weight oracle and $O(n+\sqrt{m}\log n)$ total work.

Affiliated with

Also associated with

No associations

Rating

Quantum Verification of Minimum Spanning Tree does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Quantum Verification of Minimum Spanning Tree, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Quantum Verification of Minimum Spanning Tree will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-396346