Vi presenterar en polynom-tid algoritm för att avgöra om en given ansluten graf är en icke-trivial Cartesian produkt. Metoden innebär att först representera grafen som en isometrisk subgraf av en kartesisk produkt av grafer, sedan hitta en lämplig partition av faktorerna. Den kartesiska produkten G x H av graferna G och H har som hörn paren (g, h) med g en vertex av G och h en vertex av H; (gl, hI) är ansluten med en kant till (g2' h 2 ) i G x H just när {gl' g2} är en kant av G och hI = h2' eller när g, = g2 och {h" h 2 } är en kant av H. Den kartesiska produkten medger unik faktorisering (Sabidussi [4]) men tills nyligen ingen effektiv algoritm var känd för att producera en sådan faktorisering. Om oanslutna grafer är tillåtna så är faktoriseringsproblemet minst lika svårt som 'grafisomorfism'; för, man kan avgöra om två anslutna grafer G och H är isomorfiska genom att avgöra om en graf med två hörn och ingen kant är en faktor för den osammanhängande föreningen av G och H. Frågan om det finns en polynomal algoritm för att avgöra om en ansluten graf är en icke-trivial kartesiska produkt - motsvarande, för att hitta sin unika factorization- ställdes av walesiska
En annan polyonimial-tid algoritm för anslutna grafer har självständigt upptäckts av Winkler REF.
Factoring a Graph in Polynomial Time
{'venue': 'Eur. J. Comb.', 'journal': 'Eur. J. Comb.', 'mag_field_of_study': ['Mathematics', 'Computer Science']}