For any general graph G(V,E) , the maximum matching can be calculated in O(√V.|E|) time using the following algorithm :


The following problem has 5-parts : -

1)Calculate maximum matching of Graph G

Can Tutte Matrix be used here ?

2)Calculate maximum matching of Graph G1 where G1 is the Line-Graph of graph G

3)Calculate maximum matching of Graph G2 where G2 is the Line-Graph of graph G1

4)Calculate maximum matching of Graph G3 where G3 is the Line-Graph of graph G2

5)Calculate maximum matching of Graph G4 where G4 is the Line-Graph of graph G3

Part-1 can be solved using the algorithm above.

My approach for solving part-2 is to construct G1 and then apply the algorithm on it , same for G2,G3,G4 , but the problem is that number of nodes and edges increase a lot in G1,G2,G3,G4 , if say , G has 3000 nodes and same number of edges, G3 might have more than 108/109 nodes and edges , so I cannot construct such a large graph as it will be inefficient in time and space to do it . How can solve the remaining parts efficiently ?

  • $\begingroup$ Perhaps this will help: sciencedirect.com/science/article/pii/S0012365X97001039 $\endgroup$ Apr 7, 2020 at 9:19
  • $\begingroup$ Thanks.... But I did not understand the meaning of 2-chain graph cover as they mentioned in the article. Can you answer it here : math.stackexchange.com/questions/3613889/… or explain me in the comments. $\endgroup$
    – Sexy Whore
    Apr 7, 2020 at 12:18
  • $\begingroup$ I believe it's just a path of length 2 (edges). $\endgroup$ Apr 7, 2020 at 12:34
  • $\begingroup$ But what is the exact meaning of "2-chain-graph-cover" . So confusing :( $\endgroup$
    – Sexy Whore
    Apr 7, 2020 at 15:03
  • $\begingroup$ All of these concepts, including 2-chain, are defined in the paper. $\endgroup$ Apr 7, 2020 at 15:21


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.