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.38k)
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)
Describe the Hitting Set problem
Write the first hitting set approximation algorithm.
Write the chance of it to get a right hitting set.
Prove the observation
Prove the lemma
Write the algorithm for all-pairs approximation
What is the size of E’?
prove
Analyze the run-time
