Anzeige
Erschienen in:
2015 | OriginalPaper | Buchkapitel
The Connected p-Centdian Problem on Block Graphs
verfasst von : Liying Kang, Jianjie Zhou, Erfang Shan
Erschienen in: Combinatorial Optimization and Applications
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Abstract
In this paper, we consider the problems of locating p-vertex \(X_p\) on block graphs such that the induced subgraph of the selected p vertices is connected. Two problems are proposed: one problem is to minimizes the sum of its weighted distances from all vertices to \(X_p\), another problem is to minimize the maximum distance from each vertex in \(V-X_p\) to \(X_p\) and at the same time to minimize the sum of its distances from all vertices. We prove that the first problem is linearly solvable on block graphs with unit edge length. For the second problem, it is shown that the set of Pareto-optimal solutions of the two criteria has cardinality not greater than n, and can be obtained in \(O(n^2)\) time, where n is the number of vertices of the block graph.