{"@context":["https://w3id.org/fdo/context/v1",{"schema":"https://schema.org/","prov":"http://www.w3.org/ns/prov#","fdo":"https://w3id.org/fdo/vocabulary/"}],"@id":"https://fdo.portal.mardi4nfdi.de/fdo/Q579285","@type":"DigitalObject","kernel":{"@id":"https://fdo.portal.mardi4nfdi.de/fdo/Q579285","digitalObjectType":"https://schema.org/ScholarlyArticle","primaryIdentifier":"mardi:Q579285","kernelVersion":"v1","immutable":true,"modified":"2026-01-06T14:08:37Z"},"profile":{"@context":"https://schema.org","@type":"ScholarlyArticle","@id":"https://portal.mardi4nfdi.de/entity/Q579285","name":"Factoring a graph in polynomial time","headline":"Factoring a graph in polynomial time","description":"scientific article; zbMATH DE number 4014778","url":"https://portal.mardi4nfdi.de/entity/Q579285","datePublished":"1987-00-00","author":[{"@id":"https://portal.mardi4nfdi.de/entity/Q221782"}],"publisher":[{"@id":"https://portal.mardi4nfdi.de/entity/Q166287"}],"identifier":{"@type":"PropertyValue","propertyID":"doi","value":"10.1016/S0195-6698(87)80012-4","url":"https://doi.org/10.1016/S0195-6698(87)80012-4"},"sameAs":["https://doi.org/10.1016/S0195-6698(87)80012-4"],"comment":"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)].","citation":[{"@id":"https://portal.mardi4nfdi.de/entity/Q1067411"},{"@id":"https://portal.mardi4nfdi.de/entity/Q3697031"},{"@id":"https://portal.mardi4nfdi.de/entity/Q772606"},{"@id":"https://portal.mardi4nfdi.de/entity/Q3332244"}]},"provenance":{"prov:generatedAtTime":"2026-01-06T14:08:37Z","prov:wasAttributedTo":"MaRDI Knowledge Graph"}}