The connected \(p\)-center problem on cactus graphs

DOI10.1016/j.tcs.2017.09.028zbMath1421.90124OpenAlexW2760665898MaRDI QIDQ1630992

Erfang Shan, Chun-song Bai, Li-ying Kang

Publication date: 5 December 2018

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2017.09.028

zbMATH Keywords

dynamic programminglocation problemcactus graphconnected \(p\)-center problem

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Dynamic programming (90C39)

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 ⋮ Computing the center of uncertain points on cactus graphs ⋮ The connected p-median problem on complete multi-layered graphs

Cites Work

• Unnamed Item
• Unnamed Item
• The connected \(p\)-center problem on block graphs with forbidden vertices
• Structured \(p\)-facility location problems on the line solvable in polynomial time
• A simple linear-time algorithm for computing the center of an interval graph
• Improved Complexity Bounds for Center Location Problems on Networks by Using Dynamic Data Structures
• An Algorithmic Approach to Network Location Problems. II: Thep-Medians
• Efficient algorithms for centers and medians in interval and circular-arc graphs

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