{"entities":{"Q686286":{"pageid":688135,"ns":120,"title":"Item:Q686286","lastrevid":47193121,"modified":"2025-12-31T23:24:26Z","type":"item","id":"Q686286","labels":{"en":{"language":"en","value":"Finding the prime factors of strong direct product graphs in polynomial time"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 428128"}},"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":"Q686286$B0E7F403-9EE7-4CA3-B389-98BD2C795602","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"e00751984a3991d42bea4d92e48732f1011091c5","datavalue":{"value":{"text":"Finding the prime factors of strong direct product graphs in polynomial time","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q686286$14371F5B-1386-40C6-A50B-D68C9FAFB0C1","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"655fcb21a6df3154d27b1b9eb6e92c03612f65a7","datavalue":{"value":"0786.68076","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q686286$44264170-74ED-433F-A7E0-C1FE5BFE24C6","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"8a1f69c51def004fb19943186b0c30d67e29428b","datavalue":{"value":"10.1016/0012-365X(92)90280-S","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q686286$3CB9C1BA-4442-4616-AC0C-BDED7481BC4F","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"59f503b1f6715505f2cac45fa052432796615085","datavalue":{"value":{"entity-type":"item","numeric-id":222779,"id":"Q222779"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q686286$3DD4ABD9-98A5-4DC9-85FF-7C36AFED97FA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"26746dbc33f3758ff0c811c5b77df5443ce35694","datavalue":{"value":{"entity-type":"item","numeric-id":672747,"id":"Q672747"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q686286$A0D5BD49-F962-4131-B24A-E69506265F1A","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"38665fe4ed2b835132254a58832c329597060029","datavalue":{"value":{"entity-type":"item","numeric-id":175483,"id":"Q175483"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q686286$ED3D9D28-8E79-49EA-A593-AE0A0CA70504","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"75a8b7e8c6887771540dbf878c1b8ed98975502d","datavalue":{"value":{"time":"+1993-10-14T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q686286$BAF8D5FC-EE4B-4489-B7AB-07C9D1B3B958","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"0fed6c90eb8684a1d9162d45938bda436e8619ed","datavalue":{"value":"Finite undirected connected graphs are studied. It is known that, if a graph \\(G\\) is decomposed as the strong direct product of some graphs -- denoted as \\(G=G_ 1 \\boxtimes G_ 2 \\boxtimes \\cdots \\boxtimes G_ k\\) -- and the \\(G_ i\\)'s are irreducible as for the strong direct product, then the \\(G_ i\\)'s are uniquely determined apart from isomorphy [see \\textit{W. D\u00f6rfler}, and \\textit{W. Imrich}, \u00d6sterreich. Akad. Wiss., Math.-Naturw. Kl., S.-Ber., Abt. II. 178, 247-262 (1970; Zbl 0194.562), and \\textit{R. McKenzie}, Fundamenta Math. 70, 59-101 (1971; Zbl 0228.08002)]. This fact does not imply the unambiguous labeling of a vertex \\(v\\) of \\(G\\) in the form \\((v_ 1,v_ 2,\\dots,v_ k)\\); in addition, if \\(v,w\\) are adjacent vertices of \\(G\\), then the number of equalities \\(v_ i=w_ i\\) -- from among the \\(k\\) possible ones -- is not uniquely determined.   The authors give an algorithm such that it determines the irreducible strong direct factors of a given graph \\(G\\). The time demand of this algorithm depends polynomially on the number of vertices of \\(G\\). In the first stage of the method, \\(G\\) is decomposed into the form \\(G=H \\boxtimes K_ 1 \\boxtimes K_ 2 \\boxtimes \\dots \\boxtimes K_ s\\) where any \\(K_ j\\) is a complete graph with a prime number of vertices and maximal \\(s\\). Henceforth \\(H\\) is analyzed. A lot of effort is devoted for surmounting the ambiguity features mentioned above. It is utilized that the analogous decomposition task with respect to the Cartesian product of graphs can be executed in polynomial time [see \\textit{J. Feigenbaum}, \\textit{J. Hershberger} and \\textit{A. A. Sch\u00e4ffer}, Discrete Appl. Math. 12, 123-138 (1985; Zbl 0579.68028), and \\textit{P. Winkler}, Eur. J. Comb. 8, 209-212 (1987; Zbl 0625.05050)].","type":"string"},"datatype":"string"},"type":"statement","id":"Q686286$1FEEC299-405B-4F9D-8CD8-2D0CC97CDDCA","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q686286$D61ACB4E-51DA-4857-B226-8530698B2E11","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q686286$C4945F91-3D3E-42F6-BD75-EC3911D3C4ED","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"625e55f1f2a96178239720bc1bbbe7ad21cf0a75","datavalue":{"value":"05C70","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q686286$C073370F-A86C-4920-82D3-A6FBD5450C00","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"6e8eb4d9255bcf8cb09ecad548c00a3f7795ef33","datavalue":{"value":"428128","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q686286$E4A99260-8EF7-4B4D-9EAA-B1087884A15A","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"48f499d8db0a4291b6b9339dea6180241042a03a","datavalue":{"value":"strong direct product of graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q686286$BCC5477E-2642-49FB-959E-81CA763DF1DE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"717e07228fd2e1c393def4eb7148700f88b64f60","datavalue":{"value":"decomposition algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q686286$27CE3A16-69BF-4195-8090-A335883A31A2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"267b394071cf1b5b643cd515aabcdbcae8c08f98","datavalue":{"value":"polynomial complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q686286$9B330715-94C9-47B9-B494-4B11D5F525D9","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"abaca39f57b88d5b84a55faf23983ba21a1625b6","datavalue":{"value":{"entity-type":"item","numeric-id":588092,"id":"Q588092"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q686286$35F40ACB-6E9E-4B84-935A-35DE87B73946","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":"Q686286$F8C6AB86-F128-47F6-8163-035F1CE8038A","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"59945ee6409070635cac72e0a40152e769d0b5ea","datavalue":{"value":{"entity-type":"item","numeric-id":686277,"id":"Q686277"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q686286$6FACECC4-1655-4CF5-8983-94FAD1BB80AF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2f268cfcd12ecfd4de0cebd3c52b6a3a1aa4de0b","datavalue":{"value":{"entity-type":"item","numeric-id":1210332,"id":"Q1210332"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q686286$8F2C6D0C-A666-4B9C-81BB-B5BBD85F50C7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a42b6ad9ba92a21f931f2ead3fe79588e8a6231b","datavalue":{"value":{"entity-type":"item","numeric-id":3344238,"id":"Q3344238"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q686286$5F06B79C-DA21-4B60-9BB2-64CEC0A116C9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5c87f088fb4b1b44f408220f920aef49389b3b6d","datavalue":{"value":{"entity-type":"item","numeric-id":5590666,"id":"Q5590666"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q686286$9B2859B4-6DCD-40ED-A191-88B607AE128E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f47456b6f8de962db8b84951c0f1b1ce51083463","datavalue":{"value":{"entity-type":"item","numeric-id":2551471,"id":"Q2551471"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q686286$6C3ACAD7-5CF3-4135-B30C-28AB27983B3F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8f5623ce033ee16b98147a29e4b5dcb1e8682fa0","datavalue":{"value":{"entity-type":"item","numeric-id":4020705,"id":"Q4020705"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q686286$BB76571A-19A6-4A12-92DE-17EDEF469180","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"255c900da22e43faee36db7d10bad35f785f1f5e","datavalue":{"value":{"entity-type":"item","numeric-id":1098860,"id":"Q1098860"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q686286$86D39825-1181-47D6-B11C-2429C31C3E84","rank":"normal"},{"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":"Q686286$6EBC7E9C-04EA-414F-910B-EBACC96CA842","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4c8b52e28aa1ccf7cebdfe919307958b645277f7","datavalue":{"value":{"entity-type":"item","numeric-id":3738557,"id":"Q3738557"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q686286$CE2F89AB-53D9-462C-B71D-7F59751B82E3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"98a13f1fc7727af9443b256ff0c9b5991ce3ca9e","datavalue":{"value":{"entity-type":"item","numeric-id":686292,"id":"Q686292"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q686286$4622E0BA-CF67-4AC3-AD90-DBA3CE6FB90C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7a2e623bbafa39810fbefc79df929f949240884b","datavalue":{"value":{"entity-type":"item","numeric-id":4294601,"id":"Q4294601"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q686286$021C911D-49D5-4F58-93C3-C2FE3250DC50","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"eec41273c837e017795095dfbde50dadc0dabe38","datavalue":{"value":{"entity-type":"item","numeric-id":5561941,"id":"Q5561941"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q686286$29E44EA9-EE9B-4128-81E0-A12F0C44D1A7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9c0aa581f1dfafe6b6132e86e1f518d648497852","datavalue":{"value":{"entity-type":"item","numeric-id":2547900,"id":"Q2547900"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q686286$0589FB0D-3121-41CA-9F6D-2F06C1A74EE8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f149d0a43ebbf493b394b5c107c051254b34c3a6","datavalue":{"value":{"entity-type":"item","numeric-id":5635486,"id":"Q5635486"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q686286$45FE2F6C-C64F-4EB9-A66A-16020994FD33","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9c82928db68057be5471d3d30823456e098dbc32","datavalue":{"value":{"entity-type":"item","numeric-id":5554154,"id":"Q5554154"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q686286$73075AE4-30AC-4A95-92AF-E8AFEEEF45B8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5debb489774c07261874c925d231c3f3afdf8766","datavalue":{"value":{"entity-type":"item","numeric-id":3912037,"id":"Q3912037"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q686286$35DB067C-5CF7-4010-A0EF-F8CD80759B25","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":"Q686286$1F72A236-D3DF-4382-9EAD-00F6731364E2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"68d9ae968b4ccb7416da85c51cc2b602321e151e","datavalue":{"value":{"entity-type":"item","numeric-id":686311,"id":"Q686311"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q686286$315C8FA7-BDA8-4B66-B62C-E92E6A641B7A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4d05a5de334379278631d3f0c78b0cf6c1f50b94","datavalue":{"value":{"entity-type":"item","numeric-id":1072575,"id":"Q1072575"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q686286$BF5D5050-E77D-4DFB-9479-D4A01F6176F9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"931a424c7c82eb929f664f0a0d1ddb723900b67d","datavalue":{"value":{"entity-type":"item","numeric-id":3286073,"id":"Q3286073"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q686286$BBE9DBAD-3BC2-463B-B5ED-F04A3EF3AA8E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"30ee28d0ed23e167ceb3fdd62454860bee3279de","datavalue":{"value":{"entity-type":"item","numeric-id":579285,"id":"Q579285"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q686286$5F128A39-3033-4BED-A158-12800B74F750","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"369f75ae8cd34b460d23f5bccb8b35c81fa8db51","datavalue":{"value":{"entity-type":"item","numeric-id":2940100,"id":"Q2940100"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"fc93ae6126c1ca2a919374e0aac3d635c2873796","datavalue":{"value":{"amount":"+0.8858410120010376","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":"Q686286$AA181369-E070-4F2B-9F79-ED45B06CD378","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":"b3bcc2f2fd09da6badc984715602c1ab09b23bca","datavalue":{"value":{"amount":"+0.8703554272651672","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":"Q686286$FEDB1102-B219-4726-A2EA-8971D2D9B24D","rank":"normal"},{"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":"936081dcc6f7d7a58cc5c42e506f8a47d43415d9","datavalue":{"value":{"amount":"+0.8604307770729065","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":"Q686286$1AFB1539-E717-4A1E-87ED-C478E12EFE4A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0d6caac65b1fcff62755c6583b1d8bb254bc1173","datavalue":{"value":{"entity-type":"item","numeric-id":579285,"id":"Q579285"},"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":"Q686286$45F5C7C4-1259-43CE-BA58-E78BE91B3054","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"dd5d5071f37ee73ebbd5c06d85e988bf597d6fc6","datavalue":{"value":{"entity-type":"item","numeric-id":2997605,"id":"Q2997605"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a95aef469a04b9ec1eda17992b06785e792c2903","datavalue":{"value":{"amount":"+0.8384140133857727","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":"Q686286$97CAAEA5-05CA-4AE5-8923-769658E1186D","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:686286","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:686286"}}}}}