Вопросы с тегом «graph-classes»

28
Максимальные классы, для которых наибольшее независимое множество можно найти за полиномиальное время?

В ISGCI списки более 1100 классов графов. Для многих из них мы знаем, можно ли выбрать НЕЗАВИСИМЫЙ НАБОР за полиномиальное время; их иногда называют классами IS-easy . Я хотел бы составить список максимальных классов IS-easy. Эти классы вместе образуют границу (известной) управляемости для этой...

20
Нужно ли называть матричное умножение раз, чтобы найти коготь

Коготь - это . Тривиальный алгоритм обнаружит коготь за времени. Это можно сделать в , где - показатель быстрого умножения матриц следующим образом: возьмите подграф, индуцированный для каждой вершины , и найдите треугольник в его...

16
Ссылка для (нечетных, анти-дырочных) графиков?

Графы без X - это графы, которые не содержат графов из X в качестве индуцированного подграфа. Отверстие представляет собой цикл, по крайней мере 4 -х вершин. Нечетное отверстие представляет собой отверстие с нечетным числом вершин. Antihole является дополнением дырки. Графики (нечетные дыры,...

13
Классы графов с легким гамильтоновым циклом, но NP-сложным TSP

Задача о гамильтоновом цикле (HC) состоит в том, чтобы найти цикл, который проходит через все вершины в данном неориентированном графе. Задача коммивояжера (TSP) состоит в том, чтобы найти цикл, который проходит через все вершины в данном графе, взвешенном по ребрам, и минимизирует общее...

12
Имеют ли графы «внешнего ограниченного рода» постоянную ширину дерева?

Пусть и обозначим через множество всех графов, которые могут быть вложены в поверхность рода , что все вершины расположены на внешней грани . Например, - это множество внешнепланарных графов. Может ли ширина графов в ограничена сверху некоторой функцией от ?G k k G 0 G k...

12
У этого класса графа есть имя?

Это сформулировано путем расширения пороговых графиков . Учитывая пороговый граф где C - клика, а I - независимое множество, мое расширение выглядит следующим образом: Каждая вершина v ∈ I может быть заменена новой кликой K v, такой, что вершины K v имеют такие же соседи v .( C, я)(C,I)(C,I)СCCяIIv...

9
Существует ли круговой граф без треугольников, без звездных сечений, имеющий более n ребер?

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

9
Назовите класс графа: дизъюнктное объединение клики и независимого множества

Пусть  - граф, который является несвязным объединением клики и независимого множества, то есть GGGG=Kn1+Kn2¯¯¯¯¯¯¯¯=Kn1+In2.G=Kn1+Kn2¯=Kn1+In2.G = K_{n_1} + \overline{K_{n_2}} = K_{n_1} + I_{n_2} . Класс графов всех таких графов характеризуется набором запрещенных индуцированных подграфов и, таким...