4551
правка
Ширина ленты графа: различия между версиями
Перейти к навигации
Перейти к поиску
→Постановка задачи
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 8: | Строка 8: | ||
Изначально эта задача возникла в процессе предварительной обработки разреженных симметричных квадратных матриц. Пусть A – такая матрица <math>n \times n \;</math> ; рассмотрим задачу нахождения матрицы перестановок P, такой, что все ненулевые элементы <math>P^T AP \; </math> располагаются в максимально возможно узкой полосе вблизи от диагонали. Эта задача эквивалентна задаче минимизации ширины ленты графа G, имеющего вершины {1, 2, ..., n} и содержащего ребро {u, v} в том и только том случае, когда <math>A_{u, v} \ne 0</math>. | Изначально эта задача возникла в процессе предварительной обработки разреженных симметричных квадратных матриц. Пусть A – такая матрица <math>n \times n \;</math> ; рассмотрим задачу нахождения матрицы перестановок P, такой, что все ненулевые элементы <math>P^T AP \; </math> располагаются в максимально возможно узкой полосе вблизи от диагонали. Эта задача эквивалентна задаче минимизации ширины ленты графа G, имеющего вершины {1, 2, ..., n} и содержащего ребро {u, v} в том и только том случае, когда <math>A_{u, v} \ne 0</math>. | ||
Взамен этого факта можно попытаться эффективно вычислить линейный порядок <math>\pi \;</math> , для которого <math>bw_{\pi }(G) \le A \cdot bw(G)</math>, сделав при этом [[коэффициент аппроксимации]] A минимально возможным. Было показано, что задача получения любого значения A = O(1) является NP-полной [18]. Основная сложность при нахождении ширины ленты графа заключается в том, что целевая функция представляет собой максимум по всем ребрам графа. В силу этого подход «разделяй и властвуй» для нахождения ширины ленты графа неэффективен, в отличие от таких родственных задач, как алгоритм минимального линейного ранжирования [ ] (здесь задача заключается в минимизации | Взамен этого факта можно попытаться эффективно вычислить линейный порядок <math>\pi \;</math> , для которого <math>bw_{\pi }(G) \le A \cdot bw(G)</math>, сделав при этом [[коэффициент аппроксимации]] A минимально возможным. Было показано, что задача получения любого значения A = O(1) является NP-полной [18]. Основная сложность при нахождении ширины ленты графа заключается в том, что целевая функция представляет собой максимум по всем ребрам графа. В силу этого подход «разделяй и властвуй» для нахождения ширины ленты графа неэффективен, в отличие от таких родственных задач, как алгоритм минимального линейного ранжирования [6] (здесь задача заключается в минимизации <math>\textstyle \sum_{ \{ u, v \} \in E} | \pi (u) - \pi (v) |</math>). Таким образом, требуется более глобальный алгоритм. Вначале следует обсудить нахождение хорошей нижней границы значения bw(G). | ||