Referências para Decomposição Modular

15

Quais são os bons papéis / livros para entender melhor o poder da Decomposição Modular e suas propriedades?

Estou particularmente interessado em aspectos algorítmicos da Decomposição Modular. Ouvi dizer que é possível encontrar uma decomposição modular de um gráfico em tempo linear. Existe um algoritmo relativamente simples para isso? Que tal um algoritmo não tão eficiente, mas mais simples?

ds.algorithms reference-request graph-theory graph-algorithms Vinicius dos Santos
fonte
2
o que é uma decomposição modular?
perfil completo de Suresh Venkat
2
@Suresh: pt.wikipedia.org/wiki/Modular_decomposition
David Eppstein
2
@ David David! Eu não sabia sobre eles e eles parecem legais.
Suresh Venkat
2
@ Nathann Cohen provavelmente seria a melhor pessoa para comentar sobre isso, uma vez que ele integrou o algoritmo de decomposição modular de tempo linear no SAGE. Código de Fabien de Montgolfier C: liafa.jussieu.fr/~fm/algos/index.html
András Salamon

Respostas:

10

Você deve observar um algoritmo de decomposição modular simples em tempo linear para gráficos, usando extensão de ordem, SWAT 2004 e decomposição modular em tempo linear de gráficos direcionados, Disc. Appl. Matemática. 2005 para os algoritmos de tempo linear mais simples conhecidos no gráfico não direcionado e direcionado, respectivamente.

O problema atraiu principalmente interesse teórico e os algoritmos desenvolvidos até agora são relativamente complexos. Não creio que tenha sido um esforço sustentado em direção a um algoritmo que seja realmente passível de ser implementado (ou seja, "não tão eficiente, mas mais simples").

Para sua informação, os primeiros algoritmos de tempo linear para gráficos não direcionados foram Um Novo Algoritmo Linear para Decomposição Modular. CAAP 1994 e Decomposição Modular em Tempo Linear e Orientação Transitiva Eficiente de Gráficos de Comparabilidade .

Gianluca Della Vedova
fonte
2
I like "não tão eficiente, mas simples" como um lema para fazer algoritmos trabalho experimental :)
Suresh Venkat
Implementação do autor liafa.jussieu.fr/~fm/algos/index.html .
Saadtaame
7

Philippe Gambette tem uma página na web sobre bibliografia de algoritmos de decomposição modular.

Sobre "Um algoritmo simples de decomposição modular em tempo linear para gráficos, usando extensão de ordem", Fabien de Montgolfier forneceu uma versão estendida deste artigo em seu site . Se você está interessado em variantes ou generalizações do MD, também pode encontrar alguns artigos sobre Relações Homogêneas no site dele.

Abner Huang
fonte
7

Na verdade, existe um algoritmo de decomposição modular recursiva (relativamente) simples que funciona em tempo linear. Veja: http://www.cs.utoronto.ca/~mtedder/TedderModular.pdf

Roubar
fonte
1
O algoritmo do artigo é para gráficos não direcionados.
Juho
0

Eu gosto do livro do Diestel . Explica como a decomposição modular funciona e como aplicá-la. Neste livro, também há muitas informações sobre a convexidade em um gráfico.

dpufrj
fonte