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

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

Let's say I want to use DP to group nodes in a graph. I can't directly use tree DP because the graph contains cycles. But what if, by assuming that node $$$i$$$ is grouped with node $$$j$$$ in some way, I can break a cycle and then apply tree DP?

What if the graph has many cycles? Technically, I could try all possibilities in $$$2^n$$$, but is there a blog or generalization of this idea, or a problem that uses it?

One example is this USACO problem, but it only has one cycle per connected component because it is a functional graph.

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

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

This is a good question. It leads to the concepts of tree decomposition and treewidth in graph theory and computer science. I remember that there has been a few competitive programming problems where these concepts are useful, you can probably search for them by yourself with these keywords.

  • »
    »
    7 дней назад, скрыть # ^ |
     
    Проголосовать: нравится 0 Проголосовать: не нравится

    Thank you so much