Mockexam Question 8

Mockexam Question 8

by Anthony Guinchard -
Number of replies: 2

Hello,

Regarding the ST min-cut algorithm in question 8 of the mock exam, I don’t understand why “the algorithm operates on very sparse graphs.” is a correct statement. What I thought is that since we have a node for every pixel in the image, so the algorithm is operating on a rather dense graph (rather than on a very sparse graph), do you see what I mean?

Thanks a lot in advance for your help and have a nice weekend!

Attachment Screenshot 2021-05-07 at 20.56.06.png
In reply to Anthony Guinchard

Re: Mockexam Question 8

by Michal Jan Tyszkiewicz -
A sparse graph is one that has few edges relative to how many we could have. A full graph with N nodes has O(N^2) edges. Since in ST min-cut we only have edges between adjacent pixels (let's say one to each of the four neighbors) + a couple between the source/sink and the exemplar fore/background pixels, we have O(4*N + a couple), compared to O(N^2) of a full graph. We can therefore call this graph sparse.