Problemas de celosía

10

Se ha trabajado bastante en problemas computacionales para órdenes parciales (por ejemplo, reconocimiento, número de salto, reconocimiento de gráficos de comparabilidad, etc.).

Tengo curiosidad por saber qué trabajo específico a las redes se ha realizado. He buscado alrededor y no he encontrado mucho trabajo similar para las redes.

En particular, me interesa saber si se han investigado los siguientes problemas de red:

  1. Reconocimiento de celosía: dado un DAG o un orden parcial, ¿es en realidad una celosía?

  2. Reconocimiento del gráfico de comparabilidad de celosía: dado un gráfico G no dirigido, ¿pueden orientarse los bordes de G de manera que la orientación resultante sea una red?

  3. Determinar / contar los elementos irreducibles de unión de una red

  4. Determinar si un enrejado dado es distribuido / modular

ds.algorithms reference-request graph-algorithms partial-order order-theory Servicio Travis
fuente
1
una pregunta relacionada: supongamos que la red no se presenta explícitamente, sino a través de (digamos) un oráculo del vecindario (dentro y fuera)
Suresh Venkat

Respuestas:

16

Con respecto a sus preguntas (2 + 4): un gráfico G no dirigido es el gráfico de cobertura (¡no el gráfico de comparabilidad!) De una red distribuida si es un gráfico mediano y tiene dos vértices que son complementarios (en lados opuestos de cada equivalencia de Djokovic) clase de bordes); ver Duffus, Dwight; Rival, Ivan (1983), "Gráficos orientables como redes distributivas", Proc. AMS 88 (2): 197–200. Esto se puede convertir en un algoritmo eficiente combinando un algoritmo de reconocimiento de gráfico medio (vea el artículo de Wikipedia) con un algoritmo para encontrar pares de vértices complementarios (vea el teorema 3 de arxiv: cs.DS / 0206033 ).

David Eppstein
fuente