Вопросы с тегом «cliquewidth»

23
Клик-ширина почти Cographs

(Я отправил этот вопрос в MathOverflow две недели назад, но пока без точного ответа) У меня есть вопрос о мерах ширины графа неориентированных простых графов. Хорошо известно, что cographs (графы, которые могут быть построены операциями дизъюнктного объединения и дополнения, начиная с изолированных...

15
Модульная декомпозиция и клик-ширина

Я пытаюсь понять некоторые понятия о модульной декомпозиции и графах ширины клика . В этой статье («О P4-аккуратных графах») есть доказательство того, как решать задачи оптимизации, такие как число кликов или хроматическое число, с использованием модульной декомпозиции. Решение этих проблем путем...

15
Выражение ширины клика с логарифмической глубиной

Когда нам дается древовидная декомпозиция графа с шириной w , есть несколько способов сделать его «красивым». В частности, известно, что его можно преобразовать в разложение дерева, где дерево является двоичным, а его высота равна O ( log n ) . Это может быть достигнуто при сохранении ширины...

13
Сохраняется ли ширина клики при сжатии краев?

Пусть класс графов с ограниченной шириной клика. В каждом графе в некоторые ребра сжимаются (например, случайно). Теперь ширина клики все еще ограничена?GGGGGG Если это (вообще) больше не ограничено, я был бы очень заинтересован в...

12
Задачи оптимизации MSOL на графах ограниченной ширины кликов с предикатами мощности

CMSOL - это подсчет монадической логики второго порядка, т. Е. Логики графов, в которой доменом является множество вершин и ребер, существуют предикаты для смежности вершин и вершин, существует ребро-вершина, существует количественное определение по ребрам, вершинам, наборам ребер и вершинам....