Recognizing Cartesian products in linear timeImrich, Wilfried (Avtor) Peterin, Iztok (Avtor) matematikateorija grafovkartezični produkt grafovlinearni algoritemrazcepmathematicsgraph theoryCartesian product graphslinear algorithmdecompositionWe 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.20072015-07-10 14:55:52Delo ni kategorizirano51567sl