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.

05C85 Graph algorithms (graph-theoretic aspects)
68R10 Graph theory (including graph drawing) in computer science