abhayps's blog

Maximum Independent Set
By abhayps, history, 6 years ago, In English

For what kind of graphs, finding maximum independent set is possible in polynomial time ?

  • Vote: I like it
  • +3
  • Vote: I do not like it

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I am doing my thesis these days about "treewidth". This parameter is closely related with other parameters and with perfect graphs. "In all perfect graphs, the graph coloring problem, maximum clique problem, and maximum independent set problem can all be solved in polynomial time" (taken from wikipedia)" Some perfect graphs that I am familiar with are the "bipartite"(not odd cycles) graphs and the "chordal"(not induced cycle bigger than 3) graphs.

→ Reply
»
6 years ago, # |
  Vote: I like it +6 Vote: I do not like it

I hope you have free time

→ Reply