Références pour la décomposition modulaire

15

Quels sont les bons papiers / livres pour mieux comprendre le pouvoir de la décomposition modulaire et ses propriétés?

Je m'intéresse particulièrement aux aspects algorithmiques de la décomposition modulaire. J'ai entendu dire qu'il est possible de trouver une décomposition modulaire d'un graphe en temps linéaire. Existe-t-il un algorithme relativement simple pour cela? Qu'en est-il d'un algorithme pas si efficace mais plus simple?

ds.algorithms reference-request graph-theory graph-algorithms Vinicius dos Santos
la source
2
qu'est-ce qu'une décomposition modulaire?
Suresh Venkat
2
@Suresh: en.wikipedia.org/wiki/Modular_decomposition
David Eppstein
2
@David Merci! Je ne les connaissais pas et ils sonnent bien.
Suresh Venkat
2
@Nathann Cohen serait probablement la meilleure personne pour commenter cela, car il a intégré l'algorithme de décomposition modulaire en temps linéaire dans SAGE. Code C de Fabien de Montgolfier: liafa.jussieu.fr/~fm/algos/index.html
András Salamon

Réponses:

10

Vous devriez consulter un algorithme de décomposition modulaire en temps linéaire simple pour les graphiques, utilisant l'extension de commande, SWAT 2004 et la décomposition modulaire en temps linéaire des graphiques dirigés, disque. Appl. Math. 2005 pour les algorithmes de temps linéaire connus les plus simples sur un graphique non dirigé et dirigé respectivement.

Le problème a principalement suscité un intérêt théorique et les algorithmes développés jusqu'à présent sont relativement complexes. Je ne pense pas que cela ait été un effort soutenu vers un algorithme qui soit réellement susceptible d'être implémenté (c'est-à-dire "pas si efficace mais plus simple").

Pour info, les premiers algorithmes à temps linéaire pour les graphes non orientés ont été un nouvel algorithme linéaire pour la décomposition modulaire. CAAP 1994 et décomposition modulaire en temps linéaire et orientation transitive efficace des graphiques de comparabilité .

Gianluca Della Vedova
la source
2
J'aime "pas si efficace mais plus simple" comme devise pour faire des algorithmes expérimentaux :)
Suresh Venkat
Mise en œuvre de l'auteur liafa.jussieu.fr/~fm/algos/index.html .
saadtaame
7

Philippe Gambette a une page web sur la bibliographie des algorithmes de décomposition modulaire.

À propos de "Un algorithme de décomposition modulaire en temps linéaire simple pour les graphiques, utilisant l'extension des ordres", Fabien de Montgolfier a fourni une version étendue de cet article sur son site Web . Si vous êtes intéressé par des variantes ou des généralisations de MD, vous pouvez également trouver des articles sur les relations homogènes sur son site Web.

Abner Huang
la source
7

Il existe en fait un algorithme de décomposition modulaire récursive (relativement) simple qui fonctionne en temps linéaire. Voir: http://www.cs.utoronto.ca/~mtedder/TedderModular.pdf

Rob
la source
1
L'algorithme de l'article concerne les graphiques non orientés.
Juho
0

J'aime le livre de Diestel . Il explique comment fonctionne la décomposition modulaire et comment l'appliquer. Dans ce livre, il y a aussi beaucoup d'informations sur la convexité dans un graphique.

dpufrj
la source