Graphs with connected medians

被引：31

作者：

Bandelt, HJ

Chepoi, V

机构：

[1] Univ Hamburg, Fachbereich Math, D-20146 Hamburg, Germany

[2] Univ Mediterranee, Fac Sci Luminy, Lab Informat Fondamentale, F-13288 Marseille, France

来源：

SIAM JOURNAL ON DISCRETE MATHEMATICS | 2002年 / 15卷 / 02期

关键词：

graphs; medians; local medians; majority rule; LP duality;

D O I：

10.1137/S089548019936360X

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

The median set of a graph G with weighted vertices comprises the vertices minimizing the average weighted distance to the vertices of G. We characterize the graphs in which, with respect to any nonnegative vertex weights, median sets always induce connected subgraphs. The characteristic conditions can be tested in polynomial time ( by employing linear programming) and are immediately verified for a number of specific graph classes.

引用

页码：268 / 282

页数：15

共 30 条

[1]

Arkhipova TT., 1976, KIBERNETIKA, V1, P13

[2] MEDIANS IN MEDIAN GRAPHS [J].