Recognizing Cartesian products in linear time

Imrich, Wilfried; Peterin, Iztok

| | SLO | ENG | Piškotki in zasebnost

Večja pisava | Manjša pisava

Prva stran > Izpis gradiva

Izpis gradiva

Naslov:	Recognizing Cartesian products in linear time
Avtorji:	ID Imrich, Wilfried (Avtor) ID Peterin, Iztok (Avtor)
Datoteke:	http://dx.doi.org/10.1016/j.disc.2005.09.038
Jezik:	Angleški jezik
Vrsta gradiva:	Delo ni kategorizirano
Tipologija:	1.01 - Izvirni znanstveni članek
Organizacija:	FERI - Fakulteta za elektrotehniko, računalništvo in informatiko
Opis:	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.
Ključne besede:	matematika, teorija grafov, kartezični produkt grafov, linearni algoritem, razcep, mathematics, graph theory, Cartesian product graphs, linear algorithm, decomposition
Leto izida:	2007
Št. strani:	str. 472-483
Številčenje:	Vol. 307, iss. 3-5
PID:	20.500.12556/DKUM-51567
UDK:	519.17
COBISS.SI-ID:	14180953
ISSN pri članku:	0012-365X
NUK URN:	URN:SI:UM:DK:AW4H72QF
Datum objave v DKUM:	10.07.2015
Število ogledov:	1727
Število prenosov:	136
Metapodatki:
Področja:	Ostalo
:	IMRICH, Wilfried in PETERIN, Iztok, 2007, Recognizing Cartesian products in linear time. Discrete mathematics [na spletu]. 2007. Vol. 307, no. 3–5, p. 472–483. [Dostopano 27 marec 2025]. Pridobljeno s: http://dx.doi.org/10.1016/j.disc.2005.09.038 Kopiraj citat