Houve uma quantidade considerável de trabalho em problemas computacionais para pedidos parciais (por exemplo, reconhecimento, número de salto, reconhecimento de gráfico de comparabilidade, etc ...).
Estou curioso sobre o trabalho específico para as treliças. Eu procurei e não encontrei muito trabalho semelhante para treliças.
Em particular, estou interessado em saber se os seguintes problemas de treliça foram investigados:
Reconhecimento de treliça: dado um DAG ou uma ordem parcial, é de fato uma treliça?
Reconhecimento do gráfico de comparabilidade da rede: dado um gráfico não direcionado G, as arestas de G podem ser orientadas de modo que a orientação resultante seja uma rede?
Determinando / contando os elementos irredutíveis da junção de uma treliça
Determinando se uma dada rede é distribuída / modular
fonte
Respostas:
Reponha suas perguntas (2 + 4): um gráfico não direcionado G é o gráfico de cobertura (não o gráfico de comparabilidade!) De uma rede distribuída se for um gráfico mediano e tiver dois vértices complementares (em lados opostos de cada equivalência de Djokovic) classe de arestas); ver Duffus, Dwight; Rival, Ivan (1983), "Gráficos orientáveis como redes distributivas", Proc. AMS 88 (2): 197–200. Isso pode ser transformado em um algoritmo eficiente combinando um algoritmo de reconhecimento de gráfico mediano (consulte o artigo da Wikipedia) com um algoritmo para encontrar pares complementares de vértices (consulte o teorema 3 de arxiv: cs.DS / 0206033 ).
fonte
Aqui está um link, pode ser que possa ajudá-lo. http://fc.isima.fr/~nourine/publications.php M. Habib e L. Nourine: um algoritmo de tempo linear para reconhecer redes de distribuição, RR LIRMM, no 92-012, 1992.
fonte