20.500.12556/DKUM-51567 Recognizing Cartesian products in linear time We present an algorithm that determines the prime factors of connected graphs with respect to the Cartesian product in linear time and space. This improves a result of Aurenhammer et al. [Cartesian graph factorization at logarithmic cost per edge, Comput. Complexity 2 (1992) 331-349], who compute the prime factors in ▫$O(mlog n)$▫ time, where ▫$m$▫ denotes the number of vertices of ▫$G$▫ and ▫$n$▫ the number of edges. Our algorithm is conceptually simpler. It gains its efficiency by the introduction of edge-labellings. matematika teorija grafov kartezični produkt grafov linearni algoritem razcep mathematics graph theory Cartesian product graphs linear algorithm decomposition true false false Angleški jezik Neznan jezik Delo ni kategorizirano 2015-07-10 14:55:52 2015-07-10 14:55:53 2022-05-30 03:06:25 2019-07-11 07:22:27 2007 0 0 str. 472-483 iss. 3-5 Vol. 307 2007 0000-00-00 NiDoloceno NiDoloceno NiDoloceno 0000-00-00 0000-00-00 0000-00-00 519.17 1118479 14180953 0012-365X URN:SI:UM:DK:AW4H72QF http://dx.doi.org/10.1016/j.disc.2005.09.038 1 https://dk.um.si/Dokument.php?lang=slv&id=76127 Fakulteta za elektrotehniko, računalništvo in informatiko 0 0 0