|
Dyuthi @ CUSAT >
e-SCHOLARSHIP >
Computer Applications >
Faculty >
Dr. Kannan Balakrishnan >
Please use this identifier to cite or link to this item:
http://purl.org/purl/4193
|
| Title: | Computing median and antimedian sets in median graphs |
| Authors: | Kannan, Balakrishnan
Boštjan, Brešar
Manoj, Changat
Sandi Klavžar
Matjaž, Kovše
Ajitha, Subhamathi R |
| Keywords: | Median
Antimedian
Profile
Hypercube
Isometric subgraph
Median graph
Weak contraction |
| Issue Date: | 13-Jun-2008 |
| Publisher: | Springer |
| Abstract: | The median (antimedian) set of a profile π = (u1, . . . , uk) of vertices of a
graphG is the set of vertices x that minimize (maximize) the remoteness i d(x,ui ).
Two algorithms for median graphs G of complexity O(nidim(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 |
| Description: | Algorithmica (2010) 57: 207–216
DOI 10.1007/s00453-008-9200-4 |
| URI: | http://dyuthi.cusat.ac.in/purl/4193 |
| Appears in Collections: | Dr. Kannan Balakrishnan
|
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.
|
