dc.contributor.author |
Kannan, Balakrishnan |
|
dc.contributor.author |
Boštjan, Brešar |
|
dc.contributor.author |
Manoj, Changat |
|
dc.contributor.author |
Sandi Klavžar |
|
dc.contributor.author |
Matjaž, Kovše |
|
dc.contributor.author |
Ajitha, Subhamathi R |
|
dc.date.accessioned |
2014-07-22T05:26:19Z |
|
dc.date.available |
2014-07-22T05:26:19Z |
|
dc.date.issued |
2008-06-13 |
|
dc.identifier.uri |
http://dyuthi.cusat.ac.in/purl/4193 |
|
dc.description |
Algorithmica (2010) 57: 207–216
DOI 10.1007/s00453-008-9200-4 |
en_US |
dc.description.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 |
en_US |
dc.description.sponsorship |
Cochin University of Science and Technology |
en_US |
dc.language.iso |
en |
en_US |
dc.publisher |
Springer |
en_US |
dc.subject |
Median |
en_US |
dc.subject |
Antimedian |
en_US |
dc.subject |
Profile |
en_US |
dc.subject |
Hypercube |
en_US |
dc.subject |
Isometric subgraph |
en_US |
dc.subject |
Median graph |
en_US |
dc.subject |
Weak contraction |
en_US |
dc.title |
Computing median and antimedian sets in median graphs |
en_US |
dc.type |
Article |
en_US |