Решетки проблемы

10

Была проделана большая работа по вычислительным задачам для частичных порядков (например, распознавание, число переходов, распознавание графа сравнимости и т. Д.).

Мне любопытно, какая работа, связанная с решетками, была проделана. Я искал вокруг и не нашел много похожих работ для решеток.

В частности, меня интересует, были ли исследованы следующие проблемы решетки:

  1. Распознавание решетки: с учетом DAG или частичного порядка это на самом деле решетка?

  2. Распознавание графа решетчатой ​​сравнимости: при заданном неориентированном графе G можно ли ориентировать ребра G так, чтобы результирующая ориентация была решеткой?

  3. Определение / подсчет неприводимых элементов решетки

  4. Определение, является ли данная решетка распределенной / модульной

ds.algorithms reference-request graph-algorithms partial-order order-theory Трэвис Сервис
источник
1
связанный с этим вопрос: предположим, что решетка представлена ​​не явно, а через (скажем) соседского оракула (внутри и снаружи)
Суреш Венкат

Ответы:

16

По вашим вопросам (2 + 4): неориентированный граф G - это покрывающий граф (не граф сравнимости!) Распределенной решетки, если он является медианным графом и имеет две вершины, которые дополняют друг друга (на противоположных сторонах каждой эквивалентности Джоковича). класс ребер); увидеть Даффуса, Дуайт; Соперник, Иван (1983), "Графы, ориентируемые как распределительные решетки", Учеб. AMS 88 (2): 197–200. Это можно превратить в эффективный алгоритм, объединив алгоритм распознавания медианного графа (см. Статью в Википедии) с алгоритмом поиска комплементарных пар вершин (см. Теорему 3 arxiv: cs.DS / 0206033 ).

Дэвид Эппштейн
источник
1

Вот ссылка, может быть, она может вам помочь. http://fc.isima.fr/~nourine/publications.php М. Хабиб и Л. Нурин: линейный алгоритм времени для распознавания распределительных решеток, RR LIRMM, № 92-012, 1992.

user53561
источник