Recognizing Cartesian products in linear time

Wilfried Imrich (Avtor), Iztok Peterin (Avtor)

Povzetek

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(m\log 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.

Ključne besede

matematika;teorija grafov;kartezični produkt grafov;linearni algoritem;razcep;mathematics;graph theory;Cartesian product graphs;linear algorithm;decomposition;

Podatki

Jezik:	Angleški jezik
Leto izida:	2007
Tipologija:	1.01 - Izvirni znanstveni članek
Organizacija:	UM FERI - Fakulteta za elektrotehniko, računalništvo in informatiko
UDK:	519.17
COBISS:	14180953
ISSN:	0012-365X
Št. ogledov:	47
Št. prenosov:	22
Ocena:	0 (0 glasov)
Metapodatki:

Ostali podatki

Sekundarni jezik:	Angleški jezik
Sekundarne ključne besede:	matematika;teorija grafov;kartezični produkt grafov;linearni algoritem;razcep;
URN:	URN:SI:UM:
Vrsta dela (COBISS):	Delo ni kategorizirano
Strani:	str. 472-483
Letnik:	ǂVol. ǂ307
Zvezek:	ǂiss. ǂ3-5
Čas izdaje:	2007
ID:	1472910