Difference between revisions of "TADM2E 5.17"

Latest revision as of 09:31, 31 July 2020

(a) Compare every possible set of three vertices and test if there is an edge between the three.

(b) One may be tempted to use DFS to find cycle of length 3, by maintaining an array parent[I] and check any backedge u-v whether grandparent of u is equal to v. However this is incorrect, consider the graph

A - B - C - D - A (square)

D - E - F - G - D (another square, connected to the first one through D)

A - G (edge that closes the triangle A - D - G).

DFS would produce:

A -> B - > C -> D (grandParent of D is B) -> A (nothing to do, back up the recursion to D and move to the next edge) -> E -> F -> G (grandparent of G is E)

At this point we find a cycle when considering the edge G - D, but the grandparent of D isn't connected to G. So we continue and consider A, and then the recursion ends and we process back every node till A, and consider the last edge: A -G. Since A isn't connected to the grandfather of G, we don't find the triangle.

Some possible solutions can be found in : http :// i11www.iti.uni-karlsruhe.de/extra/publications/sw-fclt-05_t.pdf

Alternative solution

1. O(|V|^3)
- If only adjacency lists are available, convert adjacency lists to the adjacency matrix
- If an adjacency matrix is available, traverse the matrix O(|V|^2) get a vertex U and an adjacent M, traverse the M row O(|V|) and check the vertices
for adjacency with U O(1)

2. O(|V|*|Е|), |V| <= |E|
- Data preparation
- - Let's analyze the case with the largest upper bound => assume that |V| = |E|
- - If an adjacency matrix is available, create additional adjacency lists O(|V|^2)
- - If adjacency lists are given, create an additional adjacency matrix O(|V| + |E|) = O(2 * |V|) by assumption ~ O(|V|)
- - At this stage, we have adjacency lists and an adjacency matrix, and each element of the adjacency lists also stores its coordinates from the adjacency matrix

- Algorithm
- - Traverse adjacency lists O(|V| + |E|) vertex U is the owner of the current list, vertex M is a list item
- - - Traversing a list owned by M O(|V|) vertex M is the owner of the list, vertex C is a list item
- - - - Checking C for adjacency with U O(1), since the coordinates of the vertices are known => row U and column C are known
- - Time complexity O(|V| + |E|) * O(|V|) * O(1) ~ O(|V|) * O(|V|) = O(|V|^2) ~ O(|V| * |E|), by assumption |V| = |E|

--Bkarpov96 (talk) 10:16, 5 July 2020 (UTC)