Un algorithme efficace pour calculer un digramme de ligne à partir d'un digramme

Question

Est-ce que quelqu'un connaît un algorithme efficace pour calculer un digramme de ligne à partir d'un digramme? . Voir http://en.wikipedia.org/wiki/Line_graph (l'article de Wikipedia mentionne le cas digraph près du fond (dans les sections Généralisations) Idéalement, je voudrais le faire dans le temps linéaire

A partir de cette section:.

• Si G est un dirigé graphique, son graphe linéaire ou son digramme linéaire a un sommet pour chaque arête de G.
• Deux sommets représentant des arêtes dirigées de u à v et de w à x dans G sont reliés par un front de uv à wx dans le digramme linéaire lorsque v =

Soit G le graphe orienté Soit L (G) le graphe linéaire dirigé

L'algorithme Je peux venir avec de production de L (G) donnée G est:

• Itérer à travers tous les bords de G pour produire les noeuds de L (G)
• Itérer à travers toutes les paires de noeuds (uv, wx) à L (G) et connecter si v = w

Ceci est un O (n^2) algorithme.

On dirait qu'il devrait y avoir un moyen de réduire cette durée à O (n). Je vais y réfléchir, mais j'ai pensé que je demanderais un débordement de pile juste au cas où il y aurait un algorithme célèbre (ou pas si célèbre) pour faire ça que je ne connais pas.

Answer 1

Hmm ... Je pense qu'il pourrait y avoir un algorithme plus efficace après quelques réflexions ... mais cela nécessiterait une bonne quantité de comptabilité et un peu de mémoire supplémentaire pour le faire. Mes pensées de base sont de faire une boucle sur tous les nœuds de G et de créer des nœuds connectés à partir des bords connectés à chaque nœud. Avec un lien supplémentaire pour garder une trace de G (bord) à L (G) (nœud), vous pouvez vous en sortir avec une seule boucle à travers les nœuds sur G.

Answer 2

Vous ne pouvez pas extuber d'O (n^2), car il y a un graphe avec un graphe linéaire avec une cardinalité des arêtes égale au carré de la cardinalité des sommets de l'original: pensez, par exemple, à un graphe avec n + 1 sommets, avec un seul sommet relié à tous les autres sommets: vous devez alors construire une clique avec n sommets, donc avec (n-1)^2 arêtes.

La complexité d'un algorithme est limitée à partir du bas par la taille de la sortie qu'il produit. Cela ne veut pas dire que nous n'avons pas à trouver d'algorithmes intelligents. J'ai Pensé à ce:

LG(LN,LE) getLinearGraph(G(N,E)) { 
    LN = EmptySet(); 
    LE = EmptySet(); 
    for (Vertex v : N) { 
    verticesToAdd = EmptySet() 
    for (Vertex i : out-degree(v) { 
     toAdd += textual-rep((v,i)); 
    } 
    LN += toAdd; 
    LE += make-clique(toAdd); 
    } 
}