The connected p-median problem on block graphs
| Autor: | Yue-Li Wang, William Chung-Kung Yen, Jia Jie Liu, Shun-Chieh Chang |
|---|---|
| Rok vydání: | 2015 |
| Předmět: |
Discrete mathematics
021103 operations research Control and Optimization Induced path 0211 other engineering and technologies Graph theory 0102 computer and information sciences 02 engineering and technology 01 natural sciences Longest path problem Metric dimension Combinatorics Modular decomposition Indifference graph 010201 computation theory & mathematics Chordal graph TheoryofComputation_ANALYSISOFALGORITHMSANDPROBLEMCOMPLEXITY Constraint satisfaction dual problem MathematicsofComputing_DISCRETEMATHEMATICS Mathematics |
| Zdroj: | Optimization Letters. 10:1191-1201 |
| ISSN: | 1862-4480 1862-4472 |
| Popis: | In this paper, we study a variant of the p-median problem on block graphs G in which the p-median is asked to be connected, and this problem is called the connected p-median problem. We first show that the connected p-median problem is NP-hard on block graphs with multiple edge weights. Then, we propose an O(n)-time algorithm for solving the problem on unit-edge-weighted block graphs, where n is the number of vertices in G. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full text from SpringerLink