1. Computing median and antimedian sets in median graphs.
- Author
-
Kannan Balakrishnan, Boštjan Brešar, Manoj Changat, Sandi Klavžar, Matjaž Kovše, and Ajitha Subhamathi
- Subjects
SET theory ,GRAPHIC methods ,COMPUTATIONAL complexity ,MATHEMATICAL functions ,ALGORITHMS ,DIMENSIONS ,MEDIAN (Mathematics) - Abstract
Abstract  The median (antimedian) set of a profile Ï=(u 1,â¦,u k ) of vertices of a graph G is the set of vertices x that minimize (maximize) the remoteness â i d(x,u i ). Two algorithms for median graphs G of complexity O(nâidim(G)) are designed, where n is the order and idim(G) the isometric dimension of G. The first algorithm computes median sets of profiles and will be in practice often faster than the other algorithm which in addition computes antimedian sets and remoteness functions and works in all partial cubes. [ABSTRACT FROM AUTHOR]
- Published
- 2010
- Full Text
- View/download PDF