Partial Star Products: A Local Covering Approach for the Recognition of Approximate Cartesian Product Graphs

被引：8

作者：

Hellmuth M. ^{[1
]}

Imrich W. ^{[2
]}

Kupka T. ^{[2
,3
]}

机构：

[1] Center for Bioinformatics, Saarland University, 66041 Saarbrücken, Building E2.1, 413

[2] Chair of Applied Mathematics, 8700 Leoben, Montanuniversität

[3] Department of Applied Mathematics, VSB-Technical University of Ostrava, 70833 Ostrava, 17

来源：

Mathematics in Computer Science | 2013年 / 7卷 / 3期

关键词：

Approximate product; Cartesian product; Partial star product; Product relation;

D O I：

10.1007/s11786-013-0156-7

中图分类号：

学科分类号：

摘要：

This paper is concerned with the recognition of approximate graph products with respect to the Cartesian product. Most graphs are prime, although they can have a rich product-like structure. The proposed algorithms are based on a local approach that covers a graph by small subgraphs, so-called partial star products, and then utilizes this information to derive the global factors and an embedding of the graph under investigation into Cartesian product graphs. © 2013 Springer Basel.

引用

页码：255 / 273

页数：18

共 23 条

[1]

Aurenhammer F., Hagauer J., Imrich W., Cartesian graph factorization at logarithmic cost per edge, Comput. Complex., 2, pp. 331-349, (1992)

[2]

Chiba N., Nishizeki T., Arboricity and subgraph listing algorithms, SIAM J. Comput., 14, 1, pp. 210-223, (1985)

[3]

Feigenbaum J., Product graphs: Some algorithmic and combinatorial results, (1986)

[4]

Feigenbaum J., Haddad R.A., On factorable extensions and subgraphs of prime graphs, SIAM J. Discrete Math., 2, pp. 197-218, (1989)

[5]

Feigenbaum J., Hershberger J., Schaffer A.A., A polynomial time algorithm for finding the prime factors of Cartesian-product graphs, Discrete Appl. Math., 12, pp. 123-138, (1985)

[6]

Graham R.L., Winkler P.M., On isometric embeddings of graphs, Trans. Am. Math. Soc., 288, 2, pp. 527-536, (1985)

[7]

Hagauer J., Zerovnik J., An algorithm for the weak reconstruction of Cartesian-product graphs, J. Combin. Inf. Syst. Sci., 24, pp. 97-103, (1999)

[8]

Hammack R., Imrich W., Klavzar S., Handbook of Product Graphs. Discrete Mathematics and Its Applications, (2011)

[9]

Hellmuth M., A local prime factor decomposition algorithm, Discrete Math., 311, 12, pp. 944-965, (2011)

[10]

Hellmuth M., Imrich W., Klockl W., Stadler P.F., Approximate graph products, Eur. J. Combin., 30, pp. 1119-1133, (2009)

← 1 2 3 →