# Finding subgraphs Flashcards

Assume G has n vertices and H has k vertices.

suggest a naive algorithm which determines whether H is an induced sub graph of G.

What is the run time?

Write the naive algorithm for finding triangles.

What its run-time? for which graph it is good?

A is the adjacency matrix.

What does A^2 represent?

write the algorithm for finding a triangle.

write the run time

What does A^3 represent?

Find a triangle in O(m^1.41) time.

Show the algorithm, correctness proof and run-time analysis.

Assume G with n vertices and H with **3k** vertices.

Write an algorithm which determines where H is an induced subgraph of G in O(n^2.38**k**)

Decribe the open question regarding **all paths**

Let A be an adjacent matrix of G, what does A^k resemble?

Let k be the minimal integer for which (A^k)i,j > 0. what does it tell us?

Define G^2.

Let d^2 denote the distances in G^2, and d to denote the distances in G.

How the adjacency matrix B of G^2 can be computed?

Write ASAP and its run-time

depth of the recursion - O(log n)

In each step we perform two matrix multiplications and two creations of matrices - O(n^2.373)

in total - O(n^2.373 * log n) = O(2.38)

For a weighted graph on limited range {1,… , M}, what is the run-time for all-pairs using matrix multiplication?

O(n^2.38 * m)

Define an alpha-additive algorithm which computes d’(u,v)