У меня есть несколько наборов и связанный граф, где элементы набора связаны, если они находятся в наборе друг с другом.Мне нужно найти порядок для элементов набора, который приведет к низкой индуцированной ширине для графа (я понимаю, что найти порядок, который дает минимальную индуцированную ширину, np-hard).
Какова лучшая эвристика для упорядочения графа для получения малой индуцированной ширины?
Есть ли способ найти хорошее упорядочение без генерации фактического графа и работы непосредственно из наборов?
Я делаю это потому, что пытаюсь реализовать алгоритм, который экспоненциально зависит от индуцированной ширины выбранного порядка.
Редактировать: некоторые определения.
Упорядоченный граф - упомянутый выше граф с общим порядком, примененным к узлам.
Родительский узел - Для данного узласмежный узел, который предшествует узлу в порядке, является родителем этого узла.
Индуцированный граф - График, полученный путем добавления ребра между любыми двумя узлами, которые являются родителями одного и того же узла.
Ширина упорядоченного графа - Наибольшее число родителей, которое имеет любой узел в упорядоченном графе.
Индуцированная ширина - Ширина индуцированного графаграф. * 1 035 *