The connected \(p\)-center problem on block graphs with forbidden vertices

DOI10.1016/j.tcs.2011.12.013zbMath1238.68064OpenAlexW2080445370MaRDI QIDQ418726

William Chung-Kung Yen

Publication date: 30 May 2012

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

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

zbMATH Keywords

NP-hardblock graphsblock degreesconnected \(p\)-centersgraphs with forbidden vertices

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Distance in graphs (05C12) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (11)

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 general facility location problem with connectivity on trees ⋮ The Connected p-Centdian Problem on Block Graphs ⋮ A linear time algorithm for connected \(p\)-centdian problem on block graphs ⋮ Approximability results for the converse connectedp-centre problem^† ⋮ The Connected p-Center Problem on Cactus Graphs ⋮ Computing the center of uncertain points on cactus graphs ⋮ Algorithms for connected \(p\)-centdian problem on block graphs ⋮ 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
• A simple heuristic for the p-centre problem
• An improved algorithm for the \(p\)-center problem on interval graphs with unit lengths
• A characterization of block graphs
• Center location problems on tree graphs with subtree-shaped customers
• Structured \(p\)-facility location problems on the line solvable in polynomial time
• The centdian subtree on tree networks
• A linear-time algorithm for solving the center problem on weighted cactus graphs
• Center problems with pos/neg weights on trees
• Efficient algorithms for center problems in cactus networks
• Asymmetric \(k\)-center with minimum coverage
• A bibliography for some fundamental problem categories in discrete location science
• A 1-center problem on the plane with uniformly distributed demand points
• A simple linear-time algorithm for computing the center of an interval graph
• What you should know about location modeling
• Asymmetric k -center is log ^* n -hard to approximate
• State of the Art—Location on Networks: A Survey. Part I: The p-Center and p-Median Problems
• Linear-Time Algorithms for Linear Programming in $R^3 $ and Related Problems
• Improved Complexity Bounds for Center Location Problems on Networks by Using Dynamic Data Structures
• An Algorithmic Approach to Network Location Problems. I: Thep-Centers
• An $O(n\log ^2 n)$ Algorithm for the kth Longest Path in a Tree with Applications to Location Problems
• AnO(log*n) Approximation Algorithm for the Asymmetricp-Center Problem
• Efficient algorithms for centers and medians in interval and circular-arc graphs
• Optimal Algorithms for the Path/Tree-Shaped Facility Location Problems in Trees
• Conditional location of path and tree shaped facilities on trees

This page was built for publication: The connected \(p\)-center problem on block graphs with forbidden vertices