Factoring a graph in polynomial time (Q579285): Difference between revisions
From MaRDI portal
Set profile property. |
ReferenceBot (talk | contribs) Changed an Item |
||
Property / cites work | |||
Property / cites work: A polynomial time algorithm for finding the prime factors of Cartesian- product graphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On Isometric Embeddings of Graphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Graph multiplication / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3332244 / rank | |||
Normal rank |
Latest revision as of 11:05, 18 June 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Factoring a graph in polynomial time |
scientific article |
Statements
Factoring a graph in polynomial time (English)
0 references
1987
0 references
The Cartesian product \(G\times H\) of graphs G and H has vertices (g,h) where g is a vertex in G and h a vertex in H. Two vertices of \(G\times H\), say \((g_ 1,h_ 1)\) and \((g_ 2,h_ 2)\), are connected by an edge in \(G\times H\), just when either \(\{g_ 1,g_ 2\}\) is an edge of G and \(h_ 1=h_ 2\), or when \(g_ 1=g_ 2\) and \(\{h_ 1,h_ 2\}\) is an edge of H. It was proved by \textit{G. Sabidussi} [Math. Z. 72, 446-457 (1960; Zbl 0093.376)] that Cartesian product admits unique factorization. The author proves that there is a polynomial time algorithm for constructing the prime factorization of a given connected graph. The same result, using completely different techniques, was proved also in [\textit{J. Feigenbaum, J. Hershberger} and \textit{A. A. Schaffer}, Discrete Appl. Math. 12, 123-138 (1985; Zbl 0579.68028)].
0 references
Cartesian product
0 references