Código implementado para calcular a largura do caminho (= número de pesquisa do nó, número de separação de vértices, espessura do intervalo)

13

Estou procurando uma implementação de um algoritmo para calcular a largura de caminho de um gráfico. É sabido que o cálculo da largura do caminho é equivalente ao cálculo do número de busca do nó, número de separação de vértices ou espessura do intervalo do gráfico. O algoritmo não precisa ser muito rápido; Quero executá-lo em gráficos com no máximo 20 vértices. Eu exijo que o algoritmo calcule exatamente a largura do caminho, em vez de fornecer uma aproximação.

Estou ciente de que existem algumas implementações para calcular a largura de árvore de um gráfico (um conceito relacionado), mas não conseguimos encontrar nenhuma para calcular a largura de caminho. Todos os ponteiros são apreciados!

ds.algorithms reference-request graph-algorithms implementation Bart Jansen
fonte

Respostas:

8

Uma implementação simples do DFS + DP foi adicionada ao SAGE 4.8 no ano passado: sage.graphs.graph_decompositions.vertex_separation.path_decomposition

O(nω2n)ω=pW(G)

Ralph Versteegen
fonte
Wouaaaaaaaaahhhh !! Como você aprendeu que foi adicionado ao Sage? É bom ver as pessoas realmente olhar o que os novos recursos do sábio são :-)
Nathann Cohen
A propósito, a documentação do módulo está lá e explica como tudo funciona: sagemath.org/doc/reference/sage/graphs/graph_decompositions/…
Nathann Cohen
Desculpe desapontar, mas na verdade não sou um usuário do SAGE; O Google encontrou seu patch contribuindo com ele. Eu contribuiria com o SAGE (eu já uso o Cython), mas acho que seria melhor contribuir para projetos de upstream (NetworkX?), Onde mais pessoas podem fazer uso dele.
Ralph Versteegen
Bem. O NetworkX não está mais "upstream" do Sage, pois não usa muito o NetworkX, a menos que você o solicite. E sendo capaz de usar outras partes da matemática, o Cython e a interface com programação linear também fazem a diferença:
P
8

Não sei sobre "uma implementação", mas confira

Largura de caminho da computação mais rápida que 2 ^ n Karol Suchan e Yngve Villanger Parametrizar e computação exata, 4º Workshop Internacional, IWPEC 2009, Copenhague, Dinamarca, Springer Verlag, Notas de aula em Ciência da Computação 5917, Páginas 324-335.

Andreas Björklund
fonte
2

Hisao Tamaki recentemente desenvolveu um algoritmo exato para a largura de caminho direcionada (WG 2011). Lá ele se refere a alguma aplicação prática bem-sucedida de sua abordagem (ISCIT 2010), então acho que ele também tem uma implementação do algoritmo.

Hisao Tamaki: Uma abordagem de decomposição de caminho direcionada para identificar exatamente atratores de redes booleanas. Simpósio Internacional de Comunicações e Tecnologias da Informação (ISCIT 2010), pp. 844-849

Hisao Tamaki: um algoritmo de tempo polinomial para largura de caminho direcionada limitada. In: 37th Workshop Internacional sobre Conceitos Teórico-Gráficos em Ciência da Computação (WG 2011), LNCS 6986, pp. 331-342.

Hermann Gruber
fonte