Реализован код для вычисления ширины пути (= номер поиска узла, номер разделения вершин, толщина интервала)

13

Я ищу реализацию алгоритма для вычисления ширины пути графа. Хорошо известно, что вычисление ширины пути эквивалентно вычислению числа поиска узла, числа разделения вершин или толщины интервала графа. Алгоритм не должен быть очень быстрым; Я хочу запустить его на графиках не более 20 вершин. Мне требуется алгоритм для точного вычисления ширины пути, а не для приближения.

Мне известно, что существуют некоторые реализации для вычисления ширины дерева графа (связанная концепция), но я не смог найти ни одного для вычисления ширины пути. Любые указатели приветствуются!

ds.algorithms reference-request graph-algorithms implementation Барт Янсен
источник

Ответы:

8

В прошлом году в SAGE 4.8 была добавлена ​​простая реализация DFS + DP: sage.graphs.graph_decompositions.vertex_separation.path_decomposition

Это реализовано в Cython (GNU GPL) здесь и здесь . Очень просто и коротко, если игнорировать все несущественное. время, когда ω = p w ( G ) . Это может быть ускорено с правилами обрезки, и особенно эвристики.О(Nω2N)ωзнак равнопвес(грамм)

Ральф Верстейген
источник
Wouaaaaaaaaahhhh !! Как вы узнали, что он был добавлен в Sage? Приятно видеть, что люди на самом деле смотрят на новые возможности Sage :-)
Натан Коэн
Кстати, документация к модулю только там, и объясняет, как все это работает: sagemath.org/doc/reference/sage/graphs/graph_decompositions/…
Натан Коэн
Извините, что разочаровал, но я на самом деле не пользователь SAGE; Google обнаружил, что ваш патч внес свой вклад. Я хотел бы внести свой вклад в SAGE (я уже использую Cython), но я чувствую, что было бы лучше внести свой вклад в проекты верхнего уровня (NetworkX?), Где больше людей могут использовать его.
Ральф Верстейген
Что ж. NetworkX больше не является «восходящим» Sage, так как он не использует NetworkX, если вы не попросите об этом. И возможность использовать другие части математики, Cython и интерфейс с линейным программированием тоже имеет значение :-P
Натанн Коэн
8

Не знаю о "реализации", но проверить

Вычислительный путь быстрее, чем 2 ^ n Параметризованные и точные вычисления Кароля Сухана и Ингве Виллангера, 4-й международный семинар, IWPEC 2009, Копенгаген, Дания, Springer Verlag, Конспект лекций в области компьютерных наук 5917, страницы 324-335.

Андреас Бьёрклунд
источник
2

Хисао Тамаки недавно разработал точный алгоритм для направленной ширины пути (WG 2011). Там он ссылается на успешное практическое применение своего подхода (ISCIT 2010), поэтому, я думаю, у него также есть реализация алгоритма.

Хисао Тамаки: направленный подход с разложением путей для точной идентификации аттракторов булевых сетей. Международный симпозиум по коммуникациям и информационным технологиям (ISCIT 2010), с. 844-849

Хисао Тамаки: Алгоритм полиномиального времени для ограниченной направленной траектории. В кн .: 37-й международный семинар по теоретико-графическим концепциям в информатике (WG 2011), LNCS 6986, с. 331-342.

Герман Грубер
источник