Referencias para la descomposición modular

15

¿Cuáles son buenos documentos / libros para comprender mejor el poder de la descomposición modular y sus propiedades?

Estoy particularmente interesado en los aspectos algorítmicos de la descomposición modular. He oído que es posible encontrar una descomposición modular de un gráfico en tiempo lineal. ¿Hay un algoritmo relativamente simple para eso? ¿Qué pasa con un algoritmo no tan eficiente pero más simple?

ds.algorithms reference-request graph-theory graph-algorithms Vinicius dos Santos
fuente
2
¿Qué es una descomposición modular?
Suresh Venkat
2
@Suresh: en.wikipedia.org/wiki/Modular_decomposition
David Eppstein
2
@David ¡Gracias! No sabía sobre ellos y suenan bien.
Suresh Venkat
2
@Nathann Cohen probablemente sería la mejor persona para comentar sobre esto, ya que integró el algoritmo de descomposición modular de tiempo lineal en SAGE. Código C de Fabien de Montgolfier: liafa.jussieu.fr/~fm/algos/index.html
András Salamon

Respuestas:

10

Debe mirar un Algoritmo de descomposición modular en tiempo lineal simple para gráficos, usando la extensión de orden, SWAT 2004 y la descomposición modular en tiempo lineal de gráficos dirigidos, Disco. Appl. Matemáticas. 2005 para los algoritmos de tiempo lineal más simples conocidos en gráficos no dirigidos y dirigidos, respectivamente.

El problema ha atraído principalmente el interés teórico y los algoritmos desarrollados hasta ahora son relativamente complejos. No creo que haya sido un esfuerzo sostenido hacia un algoritmo que realmente se pueda implementar (es decir, "no tan eficiente pero más simple").

Para su información, los primeros algoritmos de tiempo lineal para gráficos no dirigidos han sido Un nuevo algoritmo lineal para la descomposición modular. CAAP 1994 y descomposición modular en tiempo lineal y orientación transitiva eficiente de los gráficos de comparabilidad .

Gianluca Della Vedova
fuente
2
Me gusta "no tan eficiente, pero más simple" como lema para hacer el trabajo experimental de algoritmos :)
Suresh Venkat
Implementación del autor liafa.jussieu.fr/~fm/algos/index.html .
saadtaame
7

Philippe Gambette tiene una página web sobre bibliografía de algoritmos de descomposición modular.

Acerca de "Un algoritmo de descomposición modular de tiempo lineal simple para gráficos, usando la extensión de orden", Fabien de Montgolfier proporcionó una versión extendida de este documento en su sitio web . Si está interesado en variantes o generalizaciones de MD, también puede encontrar algunos documentos sobre Relaciones homogéneas en su sitio web.

Abner Huang
fuente
0

Me gusta el libro de Diestel . Explica cómo funciona la descomposición modular y cómo aplicarla. En este libro también hay mucha información sobre convexidad en un gráfico.

dpufrj
fuente