Сложность сетевой задачи о медиане на плоских решетках

А. А. Агеев


Аннотация: Плоской $n$-решеткой называют граф смежности плоской целочисленной решетки размеров $n\times n$. Показано, что сетевая задача о медиане (аналог известной задачи о $k$-медиане) на множестве плоских $n$-решеток NP-трудна.
Библиогр. 11.

УДК: 519.85

Реферативные базы данных:

• 
•