Complexity of the network median problem on planar grids

MaRDI QIDQ1920126zbMATH OpenFDO

Authors Alexander Ageev

Publication date 20 August 1996

Published in Siberian Advances in Mathematics (Search for Journal in Brave)

zbMATH Keywords

\(n\)-gridnetwork median problemplanar grid

Mathematics Subject Classification ID

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

Recommendations

• scientific article; zbMATH DE number 6288786
• On center cycles in grid graphs
• The location of median paths on grid graphs
• On the Complexity of Some Common Geometric Location Problems
• Deciding whether a grid is a topological subgraph of a planar graph is NP-complete

Cited in

(5)

• An efficient algorithm for solving the median problem on real road networks
• Relevant Network Distances for Approximate Approach to Large p-Median Problems
• Deciding whether a grid is a topological subgraph of a planar graph is NP-complete
• Deciding whether a grid is a topological subgraph of a planar graph is NP-complete
• Are there any good digraph width measures?

This page was built for publication: Complexity of the network median problem on planar grids

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1920126)