|
|||||
|
|
Computing median and antimedian sets in median graphs |
|
| Authors: | Kannan Balakrishnan Bo?tjan Bre?ar Manoj Changat Sandi Klav?ar Matja? Kov?e Ajitha R Subhamathi |
| Affiliation: | 1. Department of Computer Applications, Cochin University of Science and Technology, Cochin 22, India 2. Faculty of Electrical Engineering and Computer Science, University of Maribor, Smetanova 17, 2000, Maribor, Slovenia 3. Department of Futures Studies, University of Kerala, Trivandrum, 695034, India 4. Department of Mathematics and Computer Science, FNM, University of Maribor, Gosposvetska 84, 2000, Maribor, Slovenia 5. Institute of Mathematics, Physics and Mechanics, Jadranska 19, 1000, Ljubljana, Slovenia |
| 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. |
| Keywords: | |
| 本文献已被 SpringerLink 等数据库收录！ | |