Referencje dotyczące rozkładu modułowego

15

Jakie są dobre artykuły / książki, aby lepiej zrozumieć moc rozkładu modułowego i jego właściwości?

Szczególnie interesują mnie algorytmiczne aspekty dekompozycji modułowej. Słyszałem, że można znaleźć rozkład modułowy wykresu w czasie liniowym. Czy istnieje do tego stosunkowo prosty algorytm? Co z nie tak wydajnym, ale prostszym algorytmem?

ds.algorithms reference-request graph-theory graph-algorithms Vinicius dos Santos
źródło
2
czym jest rozkład modułowy?
Suresh Venkat
2
@Suresh: en.wikipedia.org/wiki/Modular_decomposition
David Eppstein
2
@David Thanks! Nie wiedziałem o nich i brzmią ładnie.
Suresh Venkat
2
@Nathann Cohen byłby prawdopodobnie najlepszą osobą do komentowania tego, ponieważ zintegrował algorytm dekodacji modularnej w czasie liniowym z SAGE. Kod C autorstwa Fabien de Montgolfier: liafa.jussieu.fr/~fm/algos/index.html
András Salamon

Odpowiedzi:

10

Powinieneś przyjrzeć się prostemu algorytmowi rozkładu liniowego w czasie dla wykresów, stosując rozszerzenie zamówienia, SWAT 2004 i rozkładowi modułowemu kierowanych wykresów w czasie liniowym, dysk. Appl. Matematyka 2005 dla najprostszych znanych algorytmów czasu liniowego odpowiednio na grafie niekierowanym i ukierunkowanym.

Problem ten wzbudził głównie zainteresowanie teoretyczne, a opracowane do tej pory algorytmy są stosunkowo złożone. Nie wydaje mi się, aby był to ciągły wysiłek w kierunku algorytmu, który faktycznie można wdrożyć (tj. „Nie jest tak wydajny, ale prostszy”).

FYI, pierwszymi algorytmami czasu liniowego dla grafów bezkierunkowych był Nowy algorytm liniowy dla rozkładu modułowego. CAAP 1994 i Modularny rozkład w czasie liniowym i efektywna orientacja przechodnia wykresów porównywalności .

Gianluca Della Vedova
źródło
2
Lubię motto „nie tak wydajne, ale prostsze” jako motto do wykonywania eksperymentalnych algorytmów :)
Suresh Venkat
Implementacja autora liafa.jussieu.fr/~fm/algos/index.html .
saadtaame
7

Philippe Gambette ma stronę internetową o bibliografii modułowych algorytmów dekompozycji.

O „Prostym algorytmie rozkładu liniowego w czasie dla wykresów przy użyciu rozszerzenia zamówienia” Fabien de Montgolfier opublikował na swojej stronie internetowej rozszerzoną wersję tego artykułu . Jeśli interesują Cię warianty lub uogólnienia MD, możesz także znaleźć artykuły na temat homogenicznych relacji na jego stronie internetowej.

Abner Huang
źródło
7

W rzeczywistości istnieje (stosunkowo) prosty rekurencyjny algorytm modularnego rozkładu, który działa w czasie liniowym. Zobacz: http://www.cs.utoronto.ca/~mtedder/TedderModular.pdf

Obrabować
źródło
1
Algorytm pracy dotyczy grafów bezkierunkowych.
Juho,
0

Lubię książkę Diestela . Wyjaśnia, jak działa rozkład modułowy i jak go zastosować. W tej książce jest również wiele informacji na temat wypukłości na wykresie.

dpufrj
źródło