Factoring cardinal product graphs in polynomial time

被引：33
作者：
Imrich, W [1 ]
机构：
[1] Montanuniv Leoben, Dept Math & Appl Geometry, A-8700 Leoben, Austria
来源：
DISCRETE MATHEMATICS | 1998年 / 192卷 / 1-3期
关键词：
D O I：
10.1016/S0012-365X(98)00069-7
中图分类号：
O1 [数学];
学科分类号：
0701 ; 070101 ;
摘要：
In this paper a polynomial algorithm for the prime factorization of finite, connected nonbipartite graphs with respect to the cardinal product is presented. This algorithm also decomposes finite, connected graphs into their prime factors with respect to the strong product and provides the basis for a new proof of the uniqueness of the prime factorization of finite, connected nonbipartite graphs with respect to the cardinal product. Furthermore, some of the consequences of these results and several open problems are discussed. (C) 1998 Elsevier Science B.V. All rights reserved.
引用
收藏
页码：119 / 144
页数：26
相关论文
共 28 条
[1]  
AURENHAMMER F, 1992, COMPUT COMPLEX, V2, P331
[2]  
DORFLER W, 1970, OSTERREICH AKAD W MN, V178, P247
[3]  
DORFLER W, 1973, C MATH SOC J BOL, V10, P361
[4]  
Dorfler W., 1974, GLASNIK MAT 3, V9, P15
[5]   PRODUCT GRAPH REPRESENTATIONS [J].
FEDER, T .
JOURNAL OF GRAPH THEORY, 1992, 16 (05) :467-488
[6]   FINDING THE PRIME FACTORS OF STRONG DIRECT-PRODUCT GRAPHS IN POLYNOMIAL-TIME [J].
FEIGENBAUM, J ;
SCHAFFER, AA .
DISCRETE MATHEMATICS, 1992, 109 (1-3) :77-102
[7]   A POLYNOMIAL-TIME ALGORITHM FOR FINDING THE PRIME FACTORS OF CARTESIAN-PRODUCT GRAPHS [J].
FEIGENBAUM, J ;
HERSHBERGER, J ;
SCHAFFER, AA .
DISCRETE APPLIED MATHEMATICS, 1985, 12 (02) :123-138
[8]   ON ISOMETRIC EMBEDDINGS OF GRAPHS [J].
GRAHAM, RL ;
WINKLER, PM .
TRANSACTIONS OF THE AMERICAN MATHEMATICAL SOCIETY, 1985, 288 (02) :527-536
[9]   On the weak reconstruction of Cartesian-product graphs [J].
Imrich, W ;
Zerovnik, J .
DISCRETE MATHEMATICS, 1996, 150 (1-3) :167-178
[10]   ASSOCIATIVE PRODUCTS OF GRAPHS [J].
IMRICH, W ;
IZBICKI, H .
MONATSHEFTE FUR MATHEMATIK, 1975, 80 (04) :277-281
123