I really don't know how can I evaluate working time if given is graph problem, so every idea is welcome:

3-CUT. Let’s look at graph problem 3-CUT (maximum slit), where given graph G and number k. It is necessary to determine if it is possible to divide graph vertices into three sets A, B and C. Facets uv have one destination u, that belongs to one set, but second destination v belongs to another set. Facets uv must to be at least k.

Let’s look at naive algorithm for this problem, which works as follows (Let n to be the number of vertices, but v1,…,vn to be vertices):

For every x1 ∈{1,2,3},x2 ∈{1,2,3},... , xn ∈{1,2,3}:

• take the division, where set A includes vertices vi, where xi=1, set B includes vertices vi, where xi=2 and set C includes vertices vi, where xi=3;

• m=0;

• for each facet uv: if u and v are in different sets, then m=m+1;

• if ≥k, then issues answer “yes”.

If division A,B,C, where m≥k not found, then issues answer “No”.

Let’s estimate working time of this algorithm in the form “Time is O(f(n))”. Computing model: let’s perceive one pseudo-code line as one action.

My idea is:

Task conditions suggest that all A, B, and C combinations have already been created and now combinations are looped. The algorithm is based on two cycles. In the first cycle, all vertices are loaded and think which to move. In the second cycle, this is done as long as it is no longer possible to carry over or check all possible combinations. There will be at least n steps. It runs once for every edge incident to vi. Each vertex has 2 verifications, in each end, and each vertex once. So O (n + 2m) = O (n + m) using an adjacency list. In this distribution, the number of edges marked with k is looped. If one of the endpoints u and v of the edges belongs to A and the another belongs to the B or C, then m = m + 1. So there will be at least n * m actions because there is an internal loop in the external loop where the comparison operation is performed. Time is O(nm); in worst case if n and m were the same numbers, it could be reduced to nn or O(n^2).

Is my idea correct generally?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.