Problèmes de réseau

Il y a eu pas mal de travail sur les problèmes de calcul pour les commandes partielles (par exemple, la reconnaissance, le nombre de sauts, la reconnaissance du graphe de comparabilité, etc.).

Je suis curieux de savoir quel travail spécifique aux réseaux a été fait. J'ai cherché autour et je n'ai pas trouvé beaucoup de travaux similaires pour les réseaux.

Je souhaite en particulier savoir si les problèmes de réseau suivants ont été étudiés:

1. Reconnaissance du réseau: étant donné un DAG ou un ordre partiel, s'agit-il en fait d'un réseau?

2. Reconnaissance du graphe de comparabilité du réseau: étant donné un graphique G non orienté, les bords de G peuvent-ils être orientés de telle sorte que l'orientation résultante soit un réseau?

3. Déterminer / compter les éléments irréductibles de jointure d'un réseau

4. Déterminer si un réseau donné est distribué / modulaire

Concernant vos questions (2 + 4): un graphe non orienté G est le graphe de couverture (pas le graphe de comparabilité!) D'un réseau distribué ssi c'est un graphe médian et il a deux sommets qui sont complémentaires (sur les côtés opposés de chaque équivalence de Djokovic classe d'arêtes); voir Duffus, Dwight; Rival, Ivan (1983), «Graphs orientable as distributive lattices», Proc. AMS 88 (2): 197-200. Cela peut être transformé en un algorithme efficace en combinant un algorithme de reconnaissance de graphe médian (voir l'article Wikipedia) avec un algorithme pour trouver des paires de sommets complémentaires (voir le théorème 3 d' arxiv: cs.DS / 0206033 ).

Voici un lien, peut-être qu'il peut vous aider. http://fc.isima.fr/~nourine/publications.php M. Habib et L. Nourine: A Linear Time Algorithm to Recognize Distributive Lattices, RR LIRMM, No 92-012, 1992.