{"entities":{"Q2375981":{"pageid":2386724,"ns":120,"title":"Item:Q2375981","lastrevid":51757388,"modified":"2026-01-19T21:12:41Z","type":"item","id":"Q2375981","labels":{"en":{"language":"en","value":"Fast canonical labeling of random subgraphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6180816"}},"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":"Q2375981$BA33DD15-916A-4089-AEDD-A1AF30F6B543","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"87cf6c0cd1cd54fd4278af283d0fd7f84bb4106f","datavalue":{"value":{"text":"Fast canonical labeling of random subgraphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2375981$7BA24F14-6B01-4655-B6CD-6D08CC41485B","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"86d057d14fe4d4df5acb8776235d171f52f7c00e","datavalue":{"value":"1272.05186","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2375981$DA3D0B1E-E423-4B80-996E-1B1D733AF29F","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"025ae75748666d5df5d41fccfb92ce9a1c652ac1","datavalue":{"value":"10.1134/S1064562413020154","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2375981$52C5BDD5-16D0-44A1-ADA5-1D57E9CF73B3","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"980ab1570ed3f0e2a6b92d389b91599045875476","datavalue":{"value":{"entity-type":"item","numeric-id":334408,"id":"Q334408"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2375981$22DBAB85-5FB4-4BF4-83FB-F3D2B14DB6D0","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"2bbc31fcaa3dcf49d82403ba391044fdfb104e43","datavalue":{"value":{"entity-type":"item","numeric-id":161529,"id":"Q161529"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2375981$29A02A85-FA8B-4BF1-A936-42024ED53AE1","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"e347dd775f3d7a708510685d2930f71df7b41755","datavalue":{"value":{"time":"+2013-06-25T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2375981$436A52C4-2918-42C7-B598-D081EB637AF6","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"7d7f7bb3dbcde8c92597a93c137a54c60e8668fc","datavalue":{"value":"This paper is related to the isomorphism problem between two given graphs. In particular, it has to do with the canonical labeling of graphs. It introduces the notion of a CL-rej algorithm - this is an algorithm which given a graph that belongs to an admissible class of graphs, it outputs a rearrangement of its vertices with the property that for any two isomorphic graphs that belong to that class the application of the corresponding rearrangement superimposes their edge sets. The author gives such an algorithm which operates in linear time (in the size of the input) and a random graph with edge probability \\(\\omega (\\ln^4 n /( n \\ln \\ln n ))\\) is admissible for this algorithm with probability that tends to 1 faster than any polynomial.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2375981$F1D3E5E8-00F8-471D-A459-EA2D37645C25","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"eee5ba7f50bd271f0d45cb8360d5c0d385d238ae","datavalue":{"value":{"entity-type":"item","numeric-id":490411,"id":"Q490411"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2375981$0F7A1471-FBE8-470E-BDA9-B07FC21455D3","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"4dd6b8847e09c706889ad9ef05dc0040f1c9f982","datavalue":{"value":"05C80","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2375981$885E1C66-A976-494D-B3E2-ADEF2760424D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"2e742a171e2cc4a4f154f55124e2a34e0da3eb3e","datavalue":{"value":"05C60","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2375981$9FCED059-C8B6-4118-A963-C5A9E44DFEBB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"5333d0205ccf54f8482367bfadbaa8f4afc5f8fb","datavalue":{"value":"05C78","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2375981$662823DA-A285-4DA6-BD1C-672BC525569A","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"c51d76593cb2101817f09a7018bb2cd0254a89a3","datavalue":{"value":"6180816","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2375981$6911786F-C5BB-49D8-9417-B9CA792B84FE","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5102ff1d0ab4ae24c2cb9e030acd02235ec2c2f1","datavalue":{"value":"graph isomorphism problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q2375981$D942028E-DF5A-4A4F-B7BF-FBCF2C7B8C42","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b4b0119f6240db47101561f64ed14178509f3cb2","datavalue":{"value":"canonical labelings","type":"string"},"datatype":"string"},"type":"statement","id":"Q2375981$70EA1D6D-255F-489A-AACD-832F6439233B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f4f51776dadcb1bfead92cdaa8c678dc729e342b","datavalue":{"value":"random graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q2375981$EBE07DB1-988E-4F63-B534-97CB24A1D83A","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":"Q2375981$FCF78EDE-697F-48DA-B82F-960BBB324D4D","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"a1bb63192136286ee2b68ee1b226f2d4a02b4b9e","datavalue":{"value":{"entity-type":"item","numeric-id":3901544,"id":"Q3901544"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2375981$B6ADACB7-4F82-4CE0-9590-B33C623817F6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a04e9ab387ed655198260c230c130b2e7ae3cac1","datavalue":{"value":{"entity-type":"item","numeric-id":3865476,"id":"Q3865476"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2375981$1C41D139-7306-4B95-B0CC-6B258A6557A7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4b07d6ae8072ec0b52d1a52248f558d67752e38c","datavalue":{"value":{"entity-type":"item","numeric-id":2743189,"id":"Q2743189"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2375981$C3339DA9-68F6-4B1C-A5F2-3358B4F14D4A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"65ac30b612ab6cd6e0da882a4820b600cf81fda9","datavalue":{"value":{"entity-type":"item","numeric-id":954962,"id":"Q954962"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2375981$B95272A8-AD62-4557-87A3-4D92EC78DCBF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"37cfc53170787246bb3af5924f08505f5cf54d5e","datavalue":{"value":{"entity-type":"item","numeric-id":3601166,"id":"Q3601166"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2375981$F9219A80-97E1-47B9-BBA2-69A4382B23F9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e18c0050fcb862bde59630cec236e69fb0f642cc","datavalue":{"value":{"entity-type":"item","numeric-id":5892548,"id":"Q5892548"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2375981$A0CF1A66-C58B-4724-8300-09653202FB7E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"82ed30c8ccfe86f25243bef4f5ef3d33f7956d74","datavalue":{"value":{"entity-type":"item","numeric-id":4697813,"id":"Q4697813"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2375981$C0728BB7-13A1-4B74-B73F-A1E7A3DAA2FD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cf68606a7fb3908e4427bd3091720490598c6345","datavalue":{"value":{"entity-type":"item","numeric-id":4315391,"id":"Q4315391"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2375981$70B30ACD-B1AB-430A-9986-E4C7133722D3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a397bdb25835045daa7666c6c80cc98be35fcbb9","datavalue":{"value":{"entity-type":"item","numeric-id":3989741,"id":"Q3989741"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2375981$0E19EB0F-325F-4102-9077-94C4BEE05A75","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f4463b46e06d21a07a2a3aff46effff1f493a8c3","datavalue":{"value":{"entity-type":"item","numeric-id":4027166,"id":"Q4027166"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2375981$810E85BC-3189-4B77-B570-07ACF22AAB94","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e22c74e16f2e2c0b59832c23a432ab0507b63820","datavalue":{"value":{"entity-type":"item","numeric-id":1309460,"id":"Q1309460"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2375981$CA64EAD8-CD52-490F-BF20-203E3927A330","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0e8f203f4dea338cb8d94de93d2c07c0cddb0103","datavalue":{"value":{"entity-type":"item","numeric-id":954962,"id":"Q954962"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1991577e7efc21bf80473cf7dfcecd3aa960eac7","datavalue":{"value":{"amount":"+0.8842729926109314","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":"Q2375981$5DEC54BD-8625-4456-B70B-282844F68232","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a2aa2d606c7dfe32bdd60bb3e7199e56e7921817","datavalue":{"value":{"entity-type":"item","numeric-id":3901544,"id":"Q3901544"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2bfd54c530fcabbde8fe5fedf5530d5e1621c68a","datavalue":{"value":{"amount":"+0.8496634364128113","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":"Q2375981$87C6879D-B4B9-436F-AEBF-6764DE1C3A2D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c38b7b428b4cd5a0dc9af6474dc8801c20ceb6e8","datavalue":{"value":{"entity-type":"item","numeric-id":3620818,"id":"Q3620818"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"afc2d60898bc7ed654284150eb887a6bd562a905","datavalue":{"value":{"amount":"+0.8049682378768921","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":"Q2375981$7916F8FF-4EAF-451B-B791-F97EB421BFDD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2e6c38f9fdbc746b060c5087fb9df00adc97da51","datavalue":{"value":{"entity-type":"item","numeric-id":3312272,"id":"Q3312272"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2f48c6b6045e7c1af5cdf049735045ba15604241","datavalue":{"value":{"amount":"+0.7769219279289246","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":"Q2375981$854E789F-C40D-4C4C-B644-6BB4F2086AD8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5433f9e96fe6e5b5ffd0b424c34b7a36e22317f2","datavalue":{"value":{"entity-type":"item","numeric-id":3315010,"id":"Q3315010"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"52fc495bb60464d9980192b12f16bf7906f0685c","datavalue":{"value":{"amount":"+0.7742838859558105","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":"Q2375981$5039FC51-CA49-48FB-A5F6-C82FE517BCE1","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2375981","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2375981"}}}}}