Разложение дерева для плоских графов

9

Сначала спросили по математике. Без ответов.

  1. Предположим, у меня есть плоский граф с плоским вложением, как мне найти разложение дерева?
  2. Каково оптимальное разложение дерева by- квадратной сетки? Не совсем уверен, как определить «оптимальный», но следует различать разложение с одним большим мешком и разложение с большим количеством больших мешков.dd
Ярослав Булатов
источник

Ответы:

11

Если то, что вы действительно хотите, - это хороший порядок удаления, возможно, вы ищете обобщенное вложенное рассечение . Это стратегия, которая использует хорошие разделители плоского графа, чтобы датьО(Nω/2) алгоритмы гауссовского исключения, определителя и т. д. для матриц из плоских графов.

Джейсон Мортон
источник
Интересно, что я нашел целый ряд литературы, расширяющей этот метод. Если я правильно понимаю, при оптимальном порядке исключения оптимальное разложение дерева легко
Ярослав Булатов,
13

По первому вопросу открыто, можно ли найти разложение дерева для плоских графов за полиномиальное время. Алгоритм наилучшего приближения может быть алгоритмом RatCatcher Сеймура и Томаса, который вычисляет ширину ветви плоского графа, поэтому он имеет коэффициент аппроксимации 1,5 по соотношению между шириной ветви и шириной дерева.

Для второго мы имеем следующую теорему о ширине К×К сетки:

Теорема. К×К сетка имеет ширину дерева К,

И сумки можно взять с размером К+1с общим К(К-1)мешки. Я не уверен, что это то, что вы хотите, так что не стесняйтесь делать это, если вы измените определение «оптимальный».

Сянь-Чжи Чан 張顯 之
источник
4

Если вам не нужна оптимальная декомпозиция дерева, вы можете построить декомпозицию дерева путем рекурсивного вычисления разделителей.

Суреш Венкат
источник