Computing median and antimedian sets in median graphs

Dyuthi/Manakin Repository

Computing median and antimedian sets in median graphs

Show simple item record Kannan, Balakrishnan Boštjan, Brešar Manoj, Changat Sandi Klavžar Matjaž, Kovše Ajitha, Subhamathi R 2014-07-22T05:26:19Z 2014-07-22T05:26:19Z 2008-06-13
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

Files in this item

Files Size Format View Description
Computing median and antimedian sets in median.pdf 283.6Kb PDF View/Open pdf

This item appears in the following Collection(s)

Show simple item record

Search Dyuthi

Advanced Search


My Account