Маршрутизация в отсутствие информации: различия между версиями

Рэкке использует изобретательный подход для доказательства существования такой иерархической декомпозиции. Полное описание построения не будет здесь приведено, однако полезно понимать, каким требованиям должна удовлетворять подобная декомпозиция. Во-первых, дерево T должно отражать все узкие места графа G, т.е. если существует множество значений спроса, вызывающее высокую нагруженность G, то оно должно также вызывать высокую нагруженность T. Естественный способ построения T выглядит следующим образом: начать с V, разбить V вдоль узкого места (формально – вдоль разреза с низким уровнем разреженности), рекурсивно повторить. Однако реализации этого слишком простого подхода недостаточно для успешной работы. Как будет показано ниже, дерево T также должно удовлетворять двум другим естественным условиям, называемым свойствами пропускной способности и веса и мотивированным следующим образом. Рассмотрим вершину i, соединенную с ее предком j в T. Это значит, что i должна направить поток <math>dem(S_i)</math> из <math>S_i</math>, что вызывает нагруженность <math>dem(S_i)/cap(S_i)</math> в T. Однако, когда T отображается обратно на G, весь поток, выходящий из <math>S_i</math>, должен пройти через <math>S_j</math>. Чтобы гарантировать, что ребра между <math>S_i</math> и <math>S_j</math> не будут перегружены, необходимо, чтобы пропускная способность пути из <math>S_i</math> в <math>S_j</math> была не слишком мала по сравнению с пропускной способностью путей из <math>S_i</math> в оставшуюся часть графа <math>V \backslash S_i</math>. Это условие называется ''свойством пропускной способности''. Рэкке гарантирует, что это отношение всегда составляет <math>\Omega(1 / log \; n)</math> для всех <math>S_i</math> и <math>S_j</math>, соответствующих ребрам (i, j) дерева. ''Свойство веса'' объясняется следующим образом. Рассмотрим вершину j дерева T с потомками <math>i_1, ..., i_p</math>. Свойство веса, в сущности, требует, чтобы множества <math>S_{i_1}, ..., S_{i_p}</math> были тесно связанными друг с другом, даже если они ограничены подграфом Sj. Чтобы понять, зачем это нужно, рассмотрим любую коммуникацию между вершинами, например, i1 и i2 в дереве T. Для этого необходим маршрут из i1 в j и далее в i2, и, следовательно, в графе G <math>S_{i_1}</math> не может использовать ребра, не входящие в <math>S_j</math>, для коммуникации с <math>S_{i_2}</math>. Рэкке показывает, что эти условия являются достаточными и что можно получить удовлетворяющую им декомпозицию.

Коэффициент <math>O(log^3 n</math>) в приводимой Рэкке гарантии появляется из трех источников. Первый логарифмический множитель связан с разрывом целостности [3, 13]. Второй определяется логарифмической высотой дерева, а третий связан с отбрасыванием логарифмического множителя в свойствах пропускной способности и веса.