Factoring a graph in polynomial time (Q579285): Difference between revisions
From MaRDI portal
Created a new Item |
Changed an Item |
||
Property / review text | |||
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)]. | |||
Property / review text: 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)]. / rank | |||
Normal rank | |||
Property / reviewed by | |||
Property / reviewed by: Giora Slutzki / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 05C99 / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 68R10 / rank | |||
Normal rank | |||
Property / zbMATH DE Number | |||
Property / zbMATH DE Number: 4014778 / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
Cartesian product | |||
Property / zbMATH Keywords: Cartesian product / rank | |||
Normal rank |
Revision as of 18:23, 1 July 2023
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