Recognizing Cartesian products in linear time

Imrich, Wilfried; Peterin, Iztok

| | SLO | ENG | Cookies and privacy

Bigger font | Smaller font

First page > Show document

Show document

Title:	Recognizing Cartesian products in linear time
Authors:	ID Imrich, Wilfried (Author) ID Peterin, Iztok (Author)
Files:	http://dx.doi.org/10.1016/j.disc.2005.09.038
Language:	English
Work type:	Not categorized
Typology:	1.01 - Original Scientific Article
Organization:	FERI - Faculty of Electrical Engineering and Computer Science
Abstract:	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.
Keywords:	matematika, teorija grafov, kartezični produkt grafov, linearni algoritem, razcep, mathematics, graph theory, Cartesian product graphs, linear algorithm, decomposition
Year of publishing:	2007
Number of pages:	str. 472-483
Numbering:	Vol. 307, iss. 3-5
PID:	20.500.12556/DKUM-51567
UDC:	519.17
ISSN on article:	0012-365X
COBISS.SI-ID:	14180953
NUK URN:	URN:SI:UM:DK:AW4H72QF
Publication date in DKUM:	10.07.2015
Views:	1727
Downloads:	136
Metadata:
Categories:	Misc.
:	IMRICH, Wilfried and PETERIN, Iztok, 2007, Recognizing Cartesian products in linear time. Discrete mathematics [online]. 2007. Vol. 307, no. 3–5, p. 472–483. [Accessed 27 March 2025]. Retrieved from: http://dx.doi.org/10.1016/j.disc.2005.09.038 Copy citation