Блог пользователя Nezzar

Автор Nezzar, история, 8 лет назад, По-английски

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!

  • Проголосовать: нравится
  • +26
  • Проголосовать: не нравится

»
8 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.