caa a22 4500 469033959 CHVBK 20180323132751.0 cr unu---uuuuu 170328e19921201xx s 000 0 eng 10.1007/BF01200428 doi (NATIONALLICENCE)springer-10.1007/BF01200428 Cartesian graph factorization at logarithmic cost per edge [Elektronische Daten] [F. Aurenhammer, J. Hagauer, W. Imrich] LetG be a connected graph withn vertices andm edges. We develop an algorithm that finds the (unique) prime factors ofG with respect to the Cartesian product inO(m logn) time andO(m) space. This shows that factoringG is at most as costly as sorting its edges. The algorithm gains its efficiency and practicality from using only basic properties of product graphs and simple data structures. Birkhäuser Verlag, 1992 Cartesian product graphs nationallicence Factorization nationallicence Algorithms nationallicence 68Q05C nationallicence Aurenhammer F. Institute for Theoretical Computer Science, Technische Universitaet Graz, Klosterwiesg. 32, A-8010, Graz, Austria aut Hagauer J. Institute for Theoretical Computer Science, Technische Universitaet Graz, Klosterwiesg. 32, A-8010, Graz, Austria aut Imrich W. Dept. of Mathematics and Applied Geometry, Montanuniversitaet Leoben, A-8700, Leoben, Austria aut computational complexity Birkhäuser-Verlag 2/4(1992-12-01), 331-349 1016-3328 2:4<331 1992 2 37 https://doi.org/10.1007/BF01200428 text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/BF01200428 text/html Onlinezugriff via DOI NATIONALLICENCE 700 1- Aurenhammer F. Institute for Theoretical Computer Science, Technische Universitaet Graz, Klosterwiesg. 32, A-8010, Graz, Austria aut NATIONALLICENCE 700 1- Hagauer J. Institute for Theoretical Computer Science, Technische Universitaet Graz, Klosterwiesg. 32, A-8010, Graz, Austria aut NATIONALLICENCE 700 1- Imrich W. Dept. of Mathematics and Applied Geometry, Montanuniversitaet Leoben, A-8700, Leoben, Austria aut NATIONALLICENCE 773 0- computational complexity Birkhäuser-Verlag 2/4(1992-12-01), 331-349 1016-3328 2:4<331 1992 2 37 Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer