Referensi untuk Dekomposisi Modular

15

Apa makalah / buku yang bagus untuk lebih memahami kekuatan Dekomposisi Modular dan propertinya?

Saya sangat tertarik pada aspek algoritmik Dekomposisi Modular. Saya telah mendengar bahwa adalah mungkin untuk menemukan Dekomposisi Modular dari grafik dalam waktu linier. Apakah ada algoritma yang relatif sederhana untuk itu? Bagaimana dengan algoritma yang tidak begitu efisien tetapi lebih sederhana?

ds.algorithms reference-request graph-theory graph-algorithms Vinicius dos Santos
sumber
2
apa itu dekomposisi modular?
Suresh Venkat
2
@Suresh: en.wikipedia.org/wiki/Modular_decomposition
David Eppstein
2
@ David Terima kasih! Saya tidak tahu tentang mereka dan mereka terdengar rapi.
Suresh Venkat
2
@Nathann Cohen mungkin akan menjadi orang terbaik untuk mengomentari ini, karena ia mengintegrasikan algoritma dekomposisi modular linear-time ke SAGE. Kode C Fabien de Montgolfier: liafa.jussieu.fr/~fm/algos/index.html
András Salamon

Jawaban:

10

Anda harus melihat pada Algoritma Dekomposisi Modular Linear-Waktu Sederhana untuk Grafik, Menggunakan Perpanjangan Pesanan, SWAT 2004 dan dekomposisi modular Linear-waktu dari grafik berarah, Disc. Appl. Matematika 2005 untuk algoritma linear-time paling sederhana yang diketahui pada masing-masing grafik tanpa arah dan terarah.

Masalahnya terutama menarik minat teoretis dan algoritma yang dikembangkan sejauh ini relatif kompleks. Saya tidak berpikir bahwa itu merupakan upaya berkelanjutan terhadap suatu algoritma yang sebenarnya dapat diterapkan (yaitu "tidak begitu efisien tetapi lebih sederhana").

FYI, algoritma linear-waktu pertama untuk grafik tidak terarah adalah Algoritma Linier Baru untuk Dekomposisi Modular. CAAP 1994 dan Dekomposisi Modular Linear-Waktu dan Orientasi Transitif yang Efisien dari Grafik yang Dapat Dibandingkan .

Gianluca Della Vedova
sumber
2
Saya suka "tidak begitu efisien tetapi lebih sederhana" sebagai motto untuk melakukan pekerjaan algoritma eksperimental :)
Suresh Venkat
Implementasi penulis liafa.jussieu.fr/~fm/algos/index.html .
saadtaame
7

Philippe Gambette memiliki halaman web tentang bibliografi algoritma dekomposisi modular.

Tentang "Algoritma Dekomposisi Modular Linear-Waktu Sederhana untuk Grafik, Menggunakan Perpanjangan Pesanan", Fabien de Montgolfier menyediakan versi panjang makalah ini di situs webnya . Jika Anda tertarik dengan varian atau generalisasi MD, Anda dapat menemukan beberapa makalah tentang Hubungan Homogen di situs webnya juga.

Abner Huang
sumber
7

Sebenarnya ada (relatif) algoritma dekomposisi modular rekursif sederhana yang bekerja dalam waktu linier. Lihat: http://www.cs.utoronto.ca/~mtedder/TedderModular.pdf

rampok
sumber
1
Algoritma makalah ini adalah untuk grafik yang tidak diarahkan.
Juho
0

Saya suka buku Diestel . Ini menjelaskan cara kerja dekomposisi modular dan cara menerapkannya. Dalam buku ini ada juga banyak informasi tentang kecemburuan dalam grafik.

dpufrj
sumber