Рекомендации по модульной декомпозиции

15

Что такое хорошие статьи / книги, чтобы лучше понять силу модульного разложения и его свойства?

Я особенно заинтересован в алгоритмических аспектах модульной декомпозиции. Я слышал, что можно найти модульную декомпозицию графа за линейное время. Есть ли относительно простой алгоритм для этого? А как насчет не очень эффективного, но более простого алгоритма?

ds.algorithms reference-request graph-theory graph-algorithms Виниций душ Сантуш
источник
2
что такое модульная декомпозиция?
Суреш Венкат
2
@Suresh: en.wikipedia.org/wiki/Modular_decomposition
Дэвид Эппштейн,
2
@ Дэвид Спасибо! Я не знал о них, и они звучат аккуратно.
Суреш Венкат
2
@ Натанн Коэн, вероятно, был бы лучшим человеком, чтобы прокомментировать это, так как он интегрировал алгоритм модульной декомпозиции линейного времени в SAGE. C-код Фабьена де Монгольфьера: liafa.jussieu.fr/~fm/algos/index.html
Саламон,

Ответы:

10

Вы должны взглянуть на Простой модульный алгоритм разложения линейного времени для графов, Использование расширения порядка, SWAT 2004 и Линейное время модульного разложения ориентированных графов, Disc. Appl. Математика 2005 для самых простых известных алгоритмов линейного времени на неориентированном и ориентированном графе соответственно.

Проблема в основном вызвала теоретический интерес, и алгоритмы, разработанные до сих пор, являются относительно сложными. Я не думаю, что это были постоянные усилия в направлении алгоритма, который на самом деле поддается реализации (то есть «не так эффективно, но проще»).

К вашему сведению, первые алгоритмы линейного времени для неориентированных графов были «Новый линейный алгоритм модульной декомпозиции». CAAP 1994 и линейная модульная декомпозиция и эффективная транзитивная ориентация графов сопоставимости .

Джанлука Делла Ведова
источник
2
Мне нравится "не так эффективно, но проще", как девиз для экспериментальной работы алгоритмов :)
Суреш Венкат
Автор реализации liafa.jussieu.fr/~fm/algos/index.html .
saadtaame
7

У Филиппа Гамбета есть веб-страница о библиографии алгоритмов модульной декомпозиции.

О «Простом модульном алгоритме разложения по линейному времени для графов, использующем расширение порядка», Фабьен де Монгольфье представил расширенную версию этой статьи на своем веб-сайте . Если вас интересуют варианты или обобщения MD, вы также можете найти некоторые статьи об однородных отношениях на его веб-сайте.

Абнер Хуан
источник
7

Там на самом деле является (относительно) простой рекурсивный алгоритм модульной декомпозиции , который работает в линейном времени. Смотрите: http://www.cs.utoronto.ca/~mtedder/TedderModular.pdf

обкрадывать
источник
1
Алгоритм работы предназначен для неориентированных графов.
Juho
0

Мне нравится книга Дистеля . Он объясняет, как работает модульная декомпозиция и как ее применять. В этой книге также много информации о выпуклости в графе.

dpufrj
источник