Referencje dotyczące rozkładu modułowego

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?

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 .

Istnieje ostatnia ankieta

Habib and Paul (2010). Przegląd algorytmicznych aspektów rozkładu modułowego. Computer Science Review 4 (1): 41-59 (2010)

że powinieneś sprawdzić.

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.

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

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.