Эффективный алгоритм для вычисления линейного орграфа из орграфа - PullRequest
Новая
       15

Эффективный алгоритм для вычисления линейного орграфа из орграфа

2 голосов
/ 04 июня 2009

Кто-нибудь знает эффективный алгоритм для вычисления линейного орграфа из орграфа? См. http://en.wikipedia.org/wiki/Line_graph (статья Википедии упоминает случай орграфа внизу (в разделах Обобщения). В идеале я хотел бы сделать это за линейное время.

Из этого раздела:

  • Если G - ориентированный граф, его направленный линейный граф или линейный орграф имеют одну вершину для каждого ребра G.
  • Две вершины, представляющие направленные ребра от u до v и от w до x в G, соединяются ребром от uv до wx в прямой орграфе, когда v = w.

Пусть G - ориентированный граф Пусть L (G) - ориентированный линейный граф

Алгоритм, который я могу придумать для получения L (G) с учетом G:

  • Перебрать все ребра G, чтобы получить узлы L (G)
  • Итерация по всем парам узлов (uv, wx) в L (G) и подключение, если v = w

Это алгоритм O (n ^ 2).

Похоже, должен быть способ сократить время до O (n). Я собираюсь подумать об этом, но я решил спросить переполнение стека на случай, если есть какой-то известный (или не очень) алгоритм для этого, которого я не знаю.

Ответы [ 2 ]

1 голос
/ 04 июня 2009

Вы не можете убежать из O (n ^ 2), потому что есть некоторый граф с линейным графом с количеством ребер, равным квадрату мощности вершин исходного: подумайте, для Например, в графе с n + 1 вершинами, с одной вершиной, связанной с другими всеми вершинами: вам нужно построить клику с n вершинами, то есть с (n-1) ^ 2 ребрами.

Сложность алгоритма ограничена снизу размером вывода, который он производит.

Это, конечно, не означает, что нам не нужно находить умные алгоритмы. Я думал об этом: 

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);
  }
}
1 голос
/ 04 июня 2009

Хм ... Я думаю, что, возможно, после некоторых раздумий может быть более эффективный алгоритм ... но для этого потребуется немалое количество бухгалтерии и кусок дополнительной памяти.

Мои основные мысли заключаются в том, что вы перебираете все узлы в G и создаете соединенные узлы из ребер, соединенных с каждым узлом. С помощью дополнительной ссылки для отслеживания G (ребра) и L (G) (узла) вы сможете обойтись всего одним циклом через узлы G.

...