Wilfried Imrich (Author), Iztok Peterin (Author)

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(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.

Keywords

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

Data

Language: English
Year of publishing:
Typology: 1.01 - Original Scientific Article
Organization: UM FERI - Faculty of Electrical Engineering and Computer Science
UDC: 519.17
COBISS: 14180953 Link will open in a new window
ISSN: 0012-365X
Views: 47
Downloads: 22
Average score: 0 (0 votes)
Metadata: JSON JSON-RDF JSON-LD TURTLE N-TRIPLES XML RDFA MICRODATA DC-XML DC-RDF RDF

Other data

Secondary language: English
Secondary keywords: matematika;teorija grafov;kartezični produkt grafov;linearni algoritem;razcep;
URN: URN:SI:UM:
Type (COBISS): Not categorized
Pages: str. 472-483
Volume: ǂVol. ǂ307
Issue: ǂiss. ǂ3-5
Chronology: 2007
ID: 1472910
Recommended works:
, no subtitle data available
, no subtitle data available
, no subtitle data available
, no subtitle data available