# zbMATH — the first resource for mathematics

Complexity of the network median problem on planar grids. (English. Russian original) Zbl 0848.05057
Sib. Adv. Math. 5, No. 2, 1-9 (1995); translation from Tr. Inst. Mat. SO RAN 27, 6-13, (1994).
Summary: The $$n$$-grid is defined to be the adjacency graph of the $$n \times n$$ integer lattice. A graph is called a planar grid if it is isomorphic to a subgraph of the $$n$$-grid. The paper shows that the network median problem (an analog of the well-known $$k$$-median problem) remains NP-hard when restricted to the class of $$n$$-grids.

##### MSC:
 05C85 Graph algorithms (graph-theoretic aspects) 68R10 Graph theory (including graph drawing) in computer science
##### Keywords:
$$n$$-grid; planar grid; network median problem