World's most popular travel blog for travel bloggers.

On maximum independent set of line graphs

, , No Comments
Problem Detail: 

Are there any special algorithms for maximum independent set of line graphs? Could this special case be in $\mathsf{P}$?

Asked By : Turbo
Answered By : Juho

Finding a maximum independent set in $L(G)$ is equivalent to finding a maximum matching in $G$. For more, and a fast polynomial-time algorithm that work for e.g., line graphs, see [1].

[1] Lozin, V.V. and Milanič, M., 2008. On finding augmenting graphs. Discrete Applied Mathematics, 156(13), pp.2517-2529.

Best Answer from StackOverflow

Question Source :

3200 people like this

 Download Related Notes/Documents


Post a Comment

Let us know your responses and feedback