Premium
Product graph representations
Author(s) -
Feder Tomás
Publication year - 1992
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.3190160508
Subject(s) - cartesian product , mathematics , combinatorics , graph , hierarchy , factorization , product (mathematics) , representation (politics) , discrete mathematics , algorithm , geometry , economics , market economy , politics , political science , law
We study a hierarchy of canonical representations of grpahs as subgraphs of cartesian products of graphs. This hierarchy starts with the isometric representation, includes the 2‐isometric represnetation, and ends with the cartesian prime factorization. We show that all three representations can be obtained in O ( nm ) time using O (m) space, for graphs with n vertices and m edges. The algorithms have immediate parallel versions that use n 3 processors and run in O (log 2 n ) time. © 1929 John Wiley & Sons, Inc.