Advanced Search

Query:

Fill in the form and click »Search«...

Format:

Display: entries per page entries

Zbl 1009.05055
Bandelt, Hans-Jürgen; Chepoi, Victor
Graphs with connected medians. (English)
[J] SIAM J. Discrete Math. 15, No.2, 268-282 (2002). ISSN 0895-4801; ISSN 1095-7146/e

For a nonnegative weight function $\pi$ on vertices $u$ of a finite connected graph $G$, let $$F_{\pi} (x)=\sum_u \pi(u) d(u,x)$$ where $d$ denotes the distance. The median set consists of all vertices $x$ which give a minimum of $F_{\pi} (x)$. A local median is a vertex which gives a lower value of $F_{\pi}(x)$ than any of its neighbors. This paper proves that the median set is connected for all $\pi$ if and only if the median set always equals the local median set, if and only if any two vertices can be connected by a path along which $F_{\pi}$ is peakless, as well as several other conditions. These are equivalent to a local condition which can be tested in polynomial time. These conditions are refined so that they can be applied to specific classes like the class of Helly graphs (it is proved that all Helly graphs satisfy them).
[Ki Hang Kim (Montgomery)]

MSC 2000:: *05C12 Distance in graphs
90C35 Network programming

Keywords: graphs; medians; local median; majority rule; LP duality

Comment on this Item PDF MathML XML ASCII DVI PS BibTeX Online Ordering Article Journal

	Scientific prize winners of the ICM 2010
	Overhang
	Lie groups, physics and geometry. An introduction for physicists, engineers and chemists.

Advanced Search

Zentralblatt MATH Berlin [Germany]