Estou procurando um problema que pertence a nos gráficos gerais, mas está em nos gráficos de largura de árvore delimitada. Na verdade, acho que esses problemas são mais difíceis do que usar a programação dinâmica normal em limites gráficos de largura de banda para resolvê-los.
16
Respostas:
Listar número cromático (é verdade que o gráfico tem uma coloração de vértice sempre que cada vértice obtém uma lista de k cores admissíveis?) É um problema completo de , mas solucionável em tempo linear em gráficos de largura da árvore limitada:ΠP2
http://www.ii.uib.no/~daniello/papers/EqColoring.pdf
fonte
Eu acho que 2-clique-colouring [GT19 em Schaefer e Umans ] é um exemplo. A questão é se o gráfico dado pode ser (indevidamente) de duas cores, de maneira que nenhuma de suas cliques máximas seja monocromática. Para gráficos de largura de árvore delimitada, cada clique máximo deve ocorrer dentro de uma única bolsa da decomposição da árvore, portanto, deve-se trabalhar para usar a abordagem de programação dinâmica padrão na qual os estados do programa dinâmico são duas cores da bolsa que colorem corretamente todas as cores. cliques máximos dentro da bolsa e são consistentes com os bons estados das bolsas infantis.
fonte