Name
Abstract | ||
|---|---|---|
This note describes fast algorithms for computing the prime factors of connected, non-bipartite graphs with respect to the direct product, and of connected graphs with respect to the strong product. The complexities are O(m min(n(2),Delta(3))) for the direct product, and O(m a(G)Delta) for the strong, where n is the order of the graph G to be factored, m its size, a(G) its arboricity, and Delta its maximum degree. That is, the complexities are linear in m for fixed Delta. |
Year | DOI | Venue |
|---|---|---|
2014 | 10.26493/1855-3974.320.43e | ARS MATHEMATICA CONTEMPORANEA |
Keywords | Field | DocType |
Graph products,algorithms | Discrete mathematics,Graph,Combinatorics,Direct product,Degree (graph theory),Prime factor,Arboricity,Mathematics | Journal |
Volume | Issue | ISSN |
7 | 2 | 1855-3966 |
Citations | PageRank | References |
2 | 0.39 | 4 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Richard H. Hammack | 1 | 51 | 15.00 |
| W. Imrich | 2 | 64 | 20.65 |