{"entities":{"Q1198063":{"pageid":1208812,"ns":120,"title":"Item:Q1198063","lastrevid":47107834,"modified":"2025-12-31T17:05:43Z","type":"item","id":"Q1198063","labels":{"en":{"language":"en","value":"A parallelization of Miller's \\(n^{\\log n}\\) isomorphism technique"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 92121"}},"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":"Q1198063$99E76EE1-4E92-4EA4-90C5-778147F4AE59","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"2bb277436098561a557f8f3d4703bfb5b3662403","datavalue":{"value":{"text":"A parallelization of Miller's \\(n^{\\log n}\\) isomorphism technique","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1198063$A0EBF1AF-2E01-4A51-8F9D-3288BE3BBF9F","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"bb480f7853d63b8e864c23cc5b56f68ae200293a","datavalue":{"value":"0769.05085","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1198063$A6FDC0AB-EDE2-4BFB-913F-4CB9261E9521","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"08bd928f88efe5f9093fe4539a536c5dee99f71f","datavalue":{"value":"10.1016/0020-0190(92)90243-O","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1198063$6BB294AE-6E8D-4900-8F12-F66308403A24","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"bbbdc3381c094a1abe2cf60ed445a4984b25837b","datavalue":{"value":{"entity-type":"item","numeric-id":168193,"id":"Q168193"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1198063$B73F734A-0E71-4023-BCB9-4CFB42DCB8D4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"a34a9be0a701504b022dad945dc9788685f1da06","datavalue":{"value":{"entity-type":"item","numeric-id":579264,"id":"Q579264"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1198063$937E7897-1CD8-463D-93AB-21317F19879B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"dd6d5b773c84fa19dba7066434169ec3323ce2d6","datavalue":{"value":{"entity-type":"item","numeric-id":218816,"id":"Q218816"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1198063$3D91560F-1826-4B90-A8F7-29263FD0CB5F","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"52fa7d44b58d0511cb8993765bd916aef86052d8","datavalue":{"value":{"entity-type":"item","numeric-id":63092,"id":"Q63092"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1198063$34D312D8-FEBF-4925-A38B-6B371FB684FF","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"be1a65edbb43ce1fc59464f99e70afbd93e8e2a0","datavalue":{"value":{"time":"+1993-01-16T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1198063$BE58D30A-C66F-4CBA-B70F-8AC7CE6555DE","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"08396c6d38356a6b1155a62ae022f2ec3d3f2158","datavalue":{"value":"The authors first present G. L. Miller's sequential algorithm of complexity \\(O(n^{\\log n+c})\\) for isomorphism testing of Steiner triple systems of order \\(n\\), \\(\\text{STS}(n)\\), as Algorithm Canonical, a recursive procedure returning a canonical form of an \\(\\text{STS}(n)\\). Two main steps in the algorithm have been called forcing and choosing and the forcing step is shown as the computation of a closure of a set defined in a suitable way needing at most \\(3\\log n\\) iterations.   The algorithm is then parallelized using a CREW-PRAM model needing \\(O(n^{\\log n+2})\\) processors and a total running time of \\(O((\\log n)^ 2)\\). Whether the problem lies in NC is left open.   It is also shown that both the sequential and parallel algorithms can be generalized to compute canonical forms of quasi-semigroups.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1198063$8742C669-ADE8-407B-BD34-32128D96F99D","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"749b7137f279a66a306e75e15f613231b281c1c5","datavalue":{"value":"05C85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1198063$174CB396-5A5E-4FDA-9D62-7CE072B9537F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"b65efe51b183d0f4a672427b8171cd1e14211cba","datavalue":{"value":"68W15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1198063$E18DC03C-17EF-450C-9338-9D89EBE1C32C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"3c2a2be2b4389d032db4a06f68dc2373e2a230e0","datavalue":{"value":"05B07","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1198063$3AF7473C-08FA-46C9-987B-F98ED21A1F13","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"2e742a171e2cc4a4f154f55124e2a34e0da3eb3e","datavalue":{"value":"05C60","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1198063$6371F6F9-5141-4128-9B83-66CBE4F0B4F8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a0c2591ec5b25df22c2ffdb20083debbdbf6fa8b","datavalue":{"value":"20N05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1198063$C5D421C5-006C-4F0A-8F67-68FA5CCDC3F1","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"7a9077ca131b51eb0a3d7b0d4675e45d0f1d2364","datavalue":{"value":"92121","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1198063$859CDBB1-4007-4B57-B645-EB44ED8B5C87","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"980a7b49e0ea343d488c83dde556c10474fcc9d9","datavalue":{"value":"sequential algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q1198063$D5AD4D3F-E07D-43E5-AE8C-49135DE1E389","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c5f8382ba04f9f05f645b4d0e4b9ea28f0619583","datavalue":{"value":"complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q1198063$B4C64F3F-FA3B-46F8-9970-30F5D7E05776","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ec3505d4a1a47ba6779c1bc97acbae985df00be0","datavalue":{"value":"isomorphism","type":"string"},"datatype":"string"},"type":"statement","id":"Q1198063$E0D479C7-825E-4C63-A72F-C4B7D405B91B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b44b120f22091c81b701d6bcda4ab8fdfa4992e8","datavalue":{"value":"Steiner triple systems","type":"string"},"datatype":"string"},"type":"statement","id":"Q1198063$C6A39CD7-4A72-4399-A7BD-07CEFBCCE92D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d33669a46e6c8e8b36873d1f752821b7694a60c9","datavalue":{"value":"parallel algorithms","type":"string"},"datatype":"string"},"type":"statement","id":"Q1198063$D10A8C20-4290-4F6B-913D-7B7BF2B0B4EB","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":"Q1198063$06350B50-8B9B-4911-AD0A-F9B74B2B3236","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"7b44ed555aed1fbc544de1802074fd0df13fb2c0","datavalue":{"value":{"entity-type":"item","numeric-id":1056541,"id":"Q1056541"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1198063$92CD693C-2ADC-4102-9AA2-C16D329F9F67","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"703d3a69d4e74cfc788f90d1a89a40d3e624a4ed","datavalue":{"value":{"entity-type":"item","numeric-id":3910533,"id":"Q3910533"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1198063$505D768F-8A13-4532-A4FE-1116228FE840","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f51877888332e1cb95de6bb1e59f14ab262bed3c","datavalue":{"value":{"entity-type":"item","numeric-id":3916602,"id":"Q3916602"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1198063$5A593169-C68A-4342-AC30-1C47F82CE6E0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7813f505c567a55f1367afdf1d3b942ec8129bbc","datavalue":{"value":{"entity-type":"item","numeric-id":3861412,"id":"Q3861412"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1198063$FA2CB0FF-D796-491A-AC64-26A73FE9D4DB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c855ed3ea1ed9e60e769a95784f5fae9418ea487","datavalue":{"value":{"entity-type":"item","numeric-id":3728911,"id":"Q3728911"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1198063$1F78E746-25DE-4B02-B083-631C2544A43A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5102d2dc2f2bef05eefc6a27de6ecc6de7c0761f","datavalue":{"value":{"entity-type":"item","numeric-id":1159699,"id":"Q1159699"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1198063$E4E0D1AE-9A67-4F41-AAC1-0AB044779F39","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f0154c0671b50ec0434583ab21c9846fa7528066","datavalue":{"value":{"entity-type":"item","numeric-id":5402540,"id":"Q5402540"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1198063$DE7E7B5F-5299-4499-B5A2-CB7B9758E78C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b0cab6a07051f6148650b987b28e9a69080dd7be","datavalue":{"value":{"entity-type":"item","numeric-id":3708032,"id":"Q3708032"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1198063$5A7521B7-E743-4CF8-A983-3DD0CC085222","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"39ca3e015d5a9a71c43e5d072fe10aa2d6bf2145","datavalue":{"value":{"entity-type":"item","numeric-id":4747506,"id":"Q4747506"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1198063$B96C0584-6D53-4908-8F10-085A177B03D3","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"8cb03c5730ea9dc4d634551a00b9ba2c2ce31a7c","datavalue":{"value":"https://doi.org/10.1016/0020-0190(92)90243-o","type":"string"},"datatype":"url"},"type":"statement","id":"Q1198063$948E49DD-4287-4CBA-A4EF-6E2B58827C08","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"97ec5010bafe41e361c1420471971d57f58d0023","datavalue":{"value":"W2048558076","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1198063$66182C0C-8484-4E65-8A04-9D39A300C1E3","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5571010653c1659b31ebc5540dec6c457a4e9cb8","datavalue":{"value":{"entity-type":"item","numeric-id":3708032,"id":"Q3708032"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"79a2b41963cb4c5c080be94ed2832e1e572ed3b2","datavalue":{"value":{"amount":"+0.8302245140075684","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":"Q1198063$9E5013EA-A52A-4F61-B8B0-07A138F90EEE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"afcd0019b8994b62bc7eecfafb63bd4ee249ce20","datavalue":{"value":{"entity-type":"item","numeric-id":5402540,"id":"Q5402540"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"043f85a32ba5d055b6b223073fe689abe0237be0","datavalue":{"value":{"amount":"+0.7467896342277527","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":"Q1198063$39F6EFFE-4A24-43B8-B18A-8B70F96C7555","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fafbaa85e135da3069a68977a9efd8d1bfdf9519","datavalue":{"value":{"entity-type":"item","numeric-id":3985812,"id":"Q3985812"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6b6a460f1363d8af618ae28b8ccae22b945bb6ba","datavalue":{"value":{"amount":"+0.7290806174278259","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":"Q1198063$32180B3C-E31D-4785-A94A-A38336CF9D7E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ed4cf25a6cebce65c55caf958303133f1f624bf1","datavalue":{"value":{"entity-type":"item","numeric-id":5495796,"id":"Q5495796"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b773584463798a4a5c734a96920082da7e2f90d3","datavalue":{"value":{"amount":"+0.7265921235084534","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":"Q1198063$A097381A-C0FB-465E-A51F-F78705EC280F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7b3acb4c5b3211a03d591dc27047959026a269f7","datavalue":{"value":{"entity-type":"item","numeric-id":4209267,"id":"Q4209267"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6c070094eff5de9dfd94cc06a60aa22ae87b9328","datavalue":{"value":{"amount":"+0.723678469657898","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":"Q1198063$4657B8DF-6651-472B-97EA-1329C5786181","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1198063","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1198063"}}}}}