{"entities":{"Q579285":{"pageid":581052,"ns":120,"title":"Item:Q579285","lastrevid":49087618,"modified":"2026-01-06T14:08:37Z","type":"item","id":"Q579285","labels":{"en":{"language":"en","value":"Factoring a graph in polynomial time"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4014778"}},"aliases":{},"claims":{"P31":[{"mainsnak":{"snaktype":"value","property":"P31","hash":"fd5912e4dab4b881a8eb0eb27e7893fef55176ad","datavalue":{"value":{"entity-type":"item","numeric-id":56887,"id":"Q56887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q579285$C63F37E1-E267-4E05-8E4A-B98D452CD7F1","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"07804238a419cd9ee940caa91a9017a76a9dcb98","datavalue":{"value":{"text":"Factoring a graph in polynomial time","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q579285$41EB9C17-3729-4EE3-8E8D-0D088C77BC62","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"02a252b8cdb7ba6b0603b79a421289302ec77f46","datavalue":{"value":"0625.05050","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q579285$F14F4DC9-FE2A-460F-AA39-B6BA8E8F7738","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"add1d2c07a73aef139392daf893d5e63aae2a40f","datavalue":{"value":"10.1016/S0195-6698(87)80012-4","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q579285$F6676358-55E5-4717-9314-1C0883F6CE05","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"b113bc4ac7ed430093230b872c083cde59919509","datavalue":{"value":{"entity-type":"item","numeric-id":166287,"id":"Q166287"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q579285$24A4C8FD-D6EB-4844-853B-B7360CC4E4C6","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"5ae48c61eed19d1e1e1f33f9255d5b329362d064","datavalue":{"value":{"time":"+1987-00-00T00:00:00Z","timezone":0,"before":0,"after":0,"precision":9,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q579285$4FE9D46E-BA6C-4B7F-9339-ADA7BE2FC4FE","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"5add576a8794b6acb0ee4a1ca0f104f9e2b243eb","datavalue":{"value":"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)].","type":"string"},"datatype":"string"},"type":"statement","id":"Q579285$A2FA8019-2800-46E6-B524-0C490E3482FE","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"e35cfda1c439de499de525a8a9009114d934bb37","datavalue":{"value":"05C99","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q579285$637A3178-06B6-41E1-9BF6-D64277ED5532","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q579285$83884229-D006-4FFD-B127-03758B4BFF52","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"247b57c6fa059402de7e98299a0d724de589bcd6","datavalue":{"value":"4014778","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q579285$B45619CD-C9DD-4E22-9B9C-91DC97862DE5","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c7642d8b032ac6ec79fcbf380f24fdc21e9f421e","datavalue":{"value":"Cartesian product","type":"string"},"datatype":"string"},"type":"statement","id":"Q579285$5B71EE54-0C9F-42A4-A83F-0E5C59FBA69B","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"2ed046cfa0f3aaebe7ee5a321838d2b14a94a270","datavalue":{"value":{"entity-type":"item","numeric-id":221782,"id":"Q221782"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q579285$D6123F92-7A49-43D8-B649-A29DD638FA9A","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"cb3a3ba65440da04d49f30062ed2e12f784ddb41","datavalue":{"value":{"entity-type":"item","numeric-id":235683,"id":"Q235683"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q579285$A8E6C376-EACD-4B28-8D17-545B3C054610","rank":"normal"}],"P1460":[{"mainsnak":{"snaktype":"value","property":"P1460","hash":"57f7fea50d2ce1b39b695c4a1313582eed405e38","datavalue":{"value":{"entity-type":"item","numeric-id":5976449,"id":"Q5976449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q579285$2DAAE75D-77E1-48B2-B246-1F2A721416AC","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"a5e21a0d2f846c7b5db53c68e1a2923e4c158d6a","datavalue":{"value":{"entity-type":"item","numeric-id":1067411,"id":"Q1067411"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q579285$C8140198-DB5D-4315-A9DE-5DC92F0B7498","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"67f29bec88daf336d76f38f176d5988388118c07","datavalue":{"value":{"entity-type":"item","numeric-id":3697031,"id":"Q3697031"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q579285$40E46538-4E89-448E-98A9-766FD15EF8F7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"844a42744531315d091ae549af20101536f6e872","datavalue":{"value":{"entity-type":"item","numeric-id":772606,"id":"Q772606"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q579285$6BDF6933-C197-4109-9F5E-63E028C677D9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"63a32861a403c56c114cfe96de80679a7848a878","datavalue":{"value":{"entity-type":"item","numeric-id":3332244,"id":"Q3332244"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q579285$56B79F55-0DB1-47FF-96B7-12883471466A","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9e9c08f3481635afb85425972eca5d5a5bdc0227","datavalue":{"value":{"entity-type":"item","numeric-id":1067411,"id":"Q1067411"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"cb0b6650e2b411b77828699d96f7fc8e10a52085","datavalue":{"value":{"amount":"+0.9115229845046996","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q579285$D30E183B-10E5-41C6-A8A7-624F2F807C0D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"466793425e9c271981c122817848867264f185cc","datavalue":{"value":{"entity-type":"item","numeric-id":1584444,"id":"Q1584444"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0ff12a7bf99cd92d214394fbcb103bda43eadcef","datavalue":{"value":{"amount":"+0.8881661891937256","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q579285$F0CCAF35-2586-427E-A2C1-121E80E47450","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"972a084a66ac0fad5f38d0864ba2cae6095935f0","datavalue":{"value":{"entity-type":"item","numeric-id":864136,"id":"Q864136"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e4f3141931c8694a1188745d0a3a90b791bf68a2","datavalue":{"value":{"amount":"+0.8696566224098206","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q579285$4A13FD6A-04B2-496D-B0F2-83AC4B9840D9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3b665ad5ee6a98399fb593a966f4242d7be36660","datavalue":{"value":{"entity-type":"item","numeric-id":686286,"id":"Q686286"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"56a585d0f21187873dd86f28dc25bd0ca41584ae","datavalue":{"value":{"amount":"+0.8568015098571777","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q579285$6BA8D906-6395-4927-B283-EC2A8357D9F4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"565960ebf912ef72410f5b0ec007107ab85cffe9","datavalue":{"value":{"entity-type":"item","numeric-id":1210332,"id":"Q1210332"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3c01c2b1f80e6ab43faa472567ba9815a246de0d","datavalue":{"value":{"amount":"+0.8501635789871216","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q579285$BB0159E4-4A3D-4992-972F-8C93F3EF0C8D","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:579285","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:579285"}}}}}