20.500.12556/DKUM-51566 Fast recognition of subclasses of almost-median graphs In this paper it is shown that a class of almost-median graphs that includes all planar almost-median graphs can be recognized in ▫$O(mlog n)$▫ time, where ▫$n$▫ denotes the number of vertices and ▫$m$▫ the number of edges. Moreover, planar almost-median graphs can be recognized in linear time. As a key auxiliary result we prove that all bipartite outerplanar graphs are isometric subgraphs of the hypercube and that the embedding can be effected in linear time. matematika teorija grafov skoraj medianski grafi algoritem mathematics graph theory almost-median graphs algorithm outerplanar graphs true true false Angleški jezik Slovenski jezik Članek v reviji 2015-07-10 14:55:51 2015-07-10 14:55:51 2024-05-07 14:05:44 2019-07-11 07:22:25 2007 0 0 str. 464-471 iss. 3-5 Vol. 307 2007 0000-00-00 NiDoloceno NiDoloceno NiDoloceno 0000-00-00 0000-00-00 0000-00-00 519.17 1118479 14180697 10.1016/j.disc.2006.07.011 0012-365X URN:SI:UM:DK:J5MW7BVA http://dx.doi.org/10.1016/j.disc.2006.07.011 1 https://dk.um.si/Dokument.php?lang=slv&id=76126 Pedagoška fakulteta 0 0 0