How fast Eire Greedy Degree Based and Maximal Matching Based? To understand the
ID: 3797024 • Letter: H
Question
How fast Eire Greedy Degree Based and Maximal Matching Based? To understand the growth of the running times of Greedy Degree Based and Maximal Matching Based algorithms, we want you to run these two algorithms on G(n, 0, 10/n, 0, 0) for different values of n. Use values of n = 10000, 11000, 12000, ..., 20000 and for each n generate 10 instances of G(n, 0, 10/n, 0, 0), run the two algorithms on all 10 instances, and report the mean running times for each n for both algorithms. Then plot a single graph that shows the mean running times of both algorithms as functions on n. in 2-3 sentences, discuss and explain the trends you see in this plot. If you have implemented the algorithms Greedy Degree Based and MAXIMALMATCHING-Based correctly, then the bottleneck for this experiment is likely to be the graph generation algorithm and not the vertex cover algorithms. This is because for a graph with n vertices, the natural graph generation algorithm will examine (roughly) n^2/2 pairs, which is 50 million pairs for n = 10,000. So our suggestion is to use the following idea for graph generation that approximately generates G(n, 0, 10/n, 0, 0). Note that a graph with n vertices has n(n - 1)/2 vertex pairs and since we connect each vertex pair with an edge with probability 10/n, the expected number of edges is 5 (n - 1). Let us take this expected number to be the exact number of edges. So our goal is to generate 5(n - 1) edges and we do this by generating each of the 5 (n - 1) edges by selecting the two endpoints of each edge uniformly at random from among the n vertices.Explanation / Answer
GreedyDegreeBased Algorithm
There exists a simple graph with degree sequence d1 > 0, d2 ... dn > 0 if and only if there exists one with degree sequence d2 1, . . ., dd1+1 1, dd1+2, . . ., dn.
A greedy algorithm (the HH-algorithm) to generate an actual graph with the given degree sequence d.
MaximumMatchingBased Algorithm
Given a graph G = (V,E), a matching M in G is a set of pairwise non-adjacent edges; that is, no two edges share a common vertex.
A vertex is matched (or saturated) if it is an endpoint of one of the edges in the matching. Otherwise the vertex is unmatched.
A maximal matching is a matching M of a graph G with the property that if any edge not in M is added to M, it is no longer a matching, that is, M is maximal if it is not a subset of any other matching in graph G. In other words, a matching M of a graph G is maximal if every edge in G has a non-empty intersection with at least one edge in M.
But for precision, since a degree is removed from the sequence at each iteration, there are ni+1 degrees left at the i-th iteration, so sorting is actually done in O((ni+1)log(ni+1)). The complexity is O(n2logn)
A maximum matching
A maximal matching can be found with a simple greedy algorithm. A maximum matching is also a maximal matching, and hence it is possible to find a largest maximal matching in polynomial time.A maximal matching that contains the smallest possible number of edges.
A maximal matching with k edges is an edge dominating set with k edges. Conversely, if we are given a minimum edge dominating set with k edges, we can construct a maximal matching with k edges in polynomial time. Therefore, the problem of finding a minimum maximal matching is essentially equal to the problem of finding a minimum edge dominating set.[10] Both of these two optimisation problems are known to be NP-hard; the decision versions of these problems are classical examples of NP-complete problems.
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.