Nezzar's blog

Need help on a ACM Regional question about maximal independent set
By Nezzar, history, 9 years ago, In English

Problem link: https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&category=562&page=show_problem&problem=4319

basically you are required to find a maximal independent set out of a very special graph, but I cannot find any usage on the property of the graph. Can someone give hints/solutions about this problem? Million thanks!

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

»
9 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Can you briefly explain the problem? That site is not allowed in my network (I have filters here). :P Which properties the graph have?

→ Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I think this is what you're looking for: https://en.wikipedia.org/wiki/Chordal_graph

I don't know the solution, it's just that the description seemed familiar.

→ Reply