The connected \(p\)-median problem on block graphs

DOI10.1007/s11590-015-0912-5zbMath1352.05082OpenAlexW1003564164MaRDI QIDQ315481

Yue-Li Wang, William Chung-Kung Yen, Jia-Jie Liu, Shun-Chieh Chang

Publication date: 21 September 2016

Published in: Optimization Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s11590-015-0912-5

zbMATH Keywords

complete graphsblock graphsNP-hardnessconnected \(p\)-median

Mathematics Subject Classification ID

Graph polynomials (05C31) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Signed and weighted graphs (05C22)

Related Items (5)

The inverse connected \(p\)-median problem on block graphs under various cost functions ⋮ A linear time algorithm for the \(p\)-maxian problem on trees with distance constraint ⋮ A linear time algorithm for connected \(p\)-centdian problem on block graphs ⋮ A SOLUTION ALGORITHM FOR p-MEDIAN LOCATION PROBLEM ON UNCERTAIN RANDOM NETWORKS ⋮ The connected p-median problem on complete multi-layered graphs

Uses Software

• SITATION
• MOD-DIST
• MENU-OKF

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Median problems with positive and negative weights on cycles and cacti
• The pos/neg-weighted median problem on block graphs with subgraph-shaped customers
• A polynomial method for the pos/neg weighted 3-median problem on a tree
• A linear algorithm for the pos/neg-weighted 1-median problem on a cactus
• Time bounds for selection
• An optimal algorithm for solving the 1-median problem on weighted 4-cactus graphs
• The pos/neg-weighted 1-median problem on tree graphs with subtree-shaped customers
• Median problems on wheels and cactus graphs
• An \(O(pn^ 2)\) algorithm for the \(p\)-median and related problems on tree graphs
• Solution methods for thep-median problem: An annotated bibliography
• An Algorithmic Approach to Network Location Problems. II: Thep-Medians
• Computing the 2‐median on tree networks in O(n lg n) time
• Algorithms – ESA 2005

This page was built for publication: The connected \(p\)-median problem on block graphs