Referenzen für die modulare Zerlegung

15

Was sind gute Papiere / Bücher, um die Kraft der Modularen Zerlegung und ihre Eigenschaften besser zu verstehen?

Ich interessiere mich besonders für algorithmische Aspekte der Modularen Zerlegung. Ich habe gehört, dass es möglich ist, eine modulare Zerlegung eines Graphen in linearer Zeit zu finden. Gibt es dafür einen relativ einfachen Algorithmus? Was ist mit einem nicht so effizienten, aber einfacheren Algorithmus?

ds.algorithms reference-request graph-theory graph-algorithms Vinicius dos Santos
quelle
2
Was ist eine modulare Zerlegung?
Suresh Venkat
2
@ Suresh: en.wikipedia.org/wiki/Modular_decomposition
David Eppstein
2
@ David Danke! Ich wusste nichts über sie und sie klingen ordentlich.
Suresh Venkat
2
@Nathann Cohen wäre wahrscheinlich der beste Kommentator, da er den linear-zeit-modularen Zerlegungsalgorithmus in SAGE integriert hat. C-Code von Fabien de Montgolfier: liafa.jussieu.fr/~fm/algos/index.html
András Salamon

Antworten:

10

Sie sollten sich einen einfachen modularen Zerlegungsalgorithmus für Graphen mit linearer Zeit unter Verwendung der Ordnungserweiterung, SWAT 2004 und einer modularen linearen Zerlegung gerichteter Graphen, Disc, ansehen. Appl. Mathematik. 2005 für die einfachsten bekannten linearen Zeitalgorithmen in ungerichteten bzw. gerichteten Graphen.

Das Problem hat vor allem theoretisches Interesse geweckt und die bisher entwickelten Algorithmen sind relativ komplex. Ich denke nicht, dass dies eine nachhaltige Anstrengung in Richtung eines Algorithmus war, der tatsächlich implementiert werden kann (dh "nicht so effizient, aber einfacher").

Zu Ihrer Information, die ersten linearen Zeitalgorithmen für ungerichtete Graphen waren Ein neuer linearer Algorithmus für die modulare Zerlegung. CAAP 1994 und Linear-Time Modular Decomposition und Efficient Transitive Orientation von Vergleichbarkeitsgraphen .

Gianluca Della Vedova
quelle
2
Ich mag "nicht so effizient, aber einfacher" als ein Motto für experimentelle Algorithmen :)
Suresh Venkat
Autorenimplementierung liafa.jussieu.fr/~fm/algos/index.html .
Saadtaame
7

Philippe Gambette hat eine Webseite über die Bibliographie modularer Zerlegungsalgorithmen.

Über "Ein einfacher linear-zeit-modularer Zerlegungsalgorithmus für Graphen unter Verwendung der Ordnungserweiterung" stellte Fabien de Montgolfier eine erweiterte Version dieses Papiers auf seiner Website zur Verfügung . Wenn Sie sich für Varianten oder Verallgemeinerungen von MD interessieren, finden Sie auf seiner Website auch einige Artikel zu Homogenen Beziehungen.

Abner Huang
quelle
7

Es tatsächlich ist ein (relativ) einfacher rekursiven modularer Dekompositionsalgorithmus , die in linearer Zeit arbeitet. Siehe: http://www.cs.utoronto.ca/~mtedder/TedderModular.pdf

rauben
quelle
1
Der Algorithmus des Papiers ist für ungerichtete Graphen.
Juho
0

Ich mag das Buch von Diestel . Es wird erklärt, wie die modulare Zerlegung funktioniert und wie sie angewendet wird. In diesem Buch finden Sie auch viele Informationen zur Konvexität in einem Diagramm.

dpufrj
quelle