The connected p-center problem on cactus graphs

DOI10.1016/J.TCS.2017.09.028MaRDI QIDQ1630992zbMATHOpenAlexFDO

Authors Erfang Shan, Chun-song Bai, Liying 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 programmingcactus graphlocation problemconnected \(p\)-center problem

Mathematics Subject Classification ID

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

Recommendations

• The connected \(p\)-center problem on cactus graphs
• The connected p-center problem on block graphs with forbidden vertices
• scientific article; zbMATH DE number 4173027
• scientific article; zbMATH DE number 5205606
• Efficient algorithms for center problems in cactus networks

Cites work

• scientific article; zbMATH DE number 177557 (Why is no real title available?)
• scientific article; zbMATH DE number 5205606 (Why is no real title available?)
• A simple linear-time algorithm for computing the center of an interval graph
• An Algorithmic Approach to Network Location Problems. II: Thep-Medians
• Efficient algorithms for centers and medians in interval and circular-arc graphs
• Improved Complexity Bounds for Center Location Problems on Networks by Using Dynamic Data Structures
• Structured \(p\)-facility location problems on the line solvable in polynomial time
• The connected \(p\)-center problem on block graphs with forbidden vertices

Cited in

(15)

• The obnoxious center problem on weighted cactus graphs.
• Efficient algorithms for center problems in cactus networks
• Computing the center of uncertain points on cactus graphs
• A linear time algorithm for connected \(p\)-centdian problem on block graphs
• The complete vertex \(p\)-center problem
• A simple greedy approximation algorithm for the minimum connected \(k\)-center problem
• 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
• The connected \(p\)-center problem on cactus graphs
• The connected \(p\)-center problem on block graphs with forbidden vertices
• scientific article; zbMATH DE number 4173027 (Why is no real title available?)
• Approximability results for the converse connected \(p\)-centre problem
• The 2-maxian problem on cactus graphs
• scientific article; zbMATH DE number 5205606 (Why is no real title available?)
• The connected \(p\)-median problem on complete multi-layered graphs

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

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