Оглавление
Задача о многослойности графов
-
Определение задачи о сэндвиче с графами
- Задача о сэндвиче с графами заключается в поиске графа, который принадлежит определенному семейству и находится между двумя другими графами.
- Один из графов должен быть подграфом, а другой – суперграфом искомого графа.
-
Обобщение задачи распознавания
- Задачи с многослойным графом являются обобщением задач распознавания и имеют приложения.
-
Постановка задачи о многослойности графа
- Граф G называется многослойным для пар G1 и G2, если E1 ⊆ E ⊆ E2, где E1 и E2 – обязательные и необязательные наборы ребер соответственно.
-
Вычислительная сложность задачи о многослойном графе
- Задача о многослойном графе является NP-полной для некоторых свойств графов, таких как хордовые графы и графы перестановок.
- Для некоторых классов графов задача может быть решена за полиномиальное время.
-
Статус сложности задач без H-графов
- Определен статус сложности задач о многослойном графе без H-графов для четырехвершинных графов H.
Полный текст статьи: