Name
Abstract | ||
|---|---|---|
The practical application of graph prime factorization algorithms is limited in practise by unavoidable noise in the data. A first step towards error-tolerant "approximate" prime factorization, is the development of local approaches that cover the graph by factorizable patches and then use this information to derive global factors. We present here a local, quasi-linear algorithm for the prime factorization of "locally unrefined graphs with respect to the strong product. To this end we introduce the backbone B(G) for a given graph G and show that the neighborhoods of the backbone vertices provide enough information to determine the global prime factors. Mathematics Subject Classification (2000). Primary 99Z99; Secondary 00A00. |
Year | DOI | Venue |
|---|---|---|
2009 | 10.1007/s11786-009-0073-y | Mathematics in Computer Science |
Keywords | Field | DocType |
. strong product graphs, local covering, backbone. | Factor graph,Discrete mathematics,Graph,Combinatorics,Vertex (geometry),Algorithm,Prime factor,Mathematics | Journal |
Volume | Issue | ISSN |
abs/1705.03823 | 4 | 1661-8289 |
Citations | PageRank | References |
6 | 0.51 | 3 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| marc hellmuth | 1 | 148 | 22.80 |
| Wilfried Imrich | 2 | 444 | 53.81 |
| Werner Klöckl | 3 | 14 | 2.20 |
| Peter F. Stadler | 4 | 256 | 62.77 |