О некоторых эффективно разрешимых классах сетевой задачи размещения с ограничениями на пропускные способности коммуникаций

В работе исследуется задача размещения в сетях с ограниченными пропускными способностями коммуникаций, в которой требуется разместить предприятия в вершинах заданной сети так, чтобы с минимальными затратами единовременно удовлетворить спросы всех клиентов, находящихся в вершинах сети. Рассматриваются постановки задачи с делимыми спросами, где спрос клиента может быть удовлетворен несколькими предприятиями совместно, и неделимыми спросами, тогда спрос клиента должен быть целиком удовлетворен одним предприятием. В работе показано, что задача с неделимыми спросами NP-трудна, даже если заданная сеть является простым путем, и NP-трудна в сильном смысле, если сеть — дерево. Задача с делимыми спросами слабо NP-трудна на деревьях. Для этой задачи в работе предложен псевдополиномиальный алгоритм решения на графах с древесной шириной, ограниченной константой, а также представлен линейный алгоритм для случая, когда граф сети является простым путем.