{"entities":{"Q424856":{"pageid":426623,"ns":120,"title":"Item:Q424856","lastrevid":61770876,"modified":"2026-04-11T01:32:53Z","type":"item","id":"Q424856","labels":{"en":{"language":"en","value":"Computing braid groups of graphs with applications to robot motion planning"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6043100"}},"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":"Q424856$D9974A8B-D520-4F2D-8DFC-68B7D1B0059E","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"f69294e610d22850c394b8f4fe2e884b1d90f99f","datavalue":{"value":{"text":"Computing braid groups of graphs with applications to robot motion planning","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q424856$62EC198E-626A-4CF9-8485-3BCFBB20A8E9","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"f3506a4b1c7b455bf1bba5a545006c0fe0d4af7e","datavalue":{"value":"1244.57009","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q424856$04039CC6-DEAA-4A9D-8A73-B942A0F6470E","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"f1a232faaaf1e464a5a121e04ea4154ec920ed45","datavalue":{"value":{"entity-type":"item","numeric-id":424855,"id":"Q424855"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q424856$4621FDB5-782F-4FE3-A6E1-69083EC8E801","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"1e22c5b89240190fc74b760088a55141cf0fb60b","datavalue":{"value":{"entity-type":"item","numeric-id":180135,"id":"Q180135"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q424856$F6F7E5C9-8C80-4797-8099-DED9088B201A","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"484bde1046a1f6e9a3ef6ce86a1d916789aecd5b","datavalue":{"value":{"time":"+2012-06-06T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q424856$EFA049FB-458B-4C2F-80BC-C5AB2A9F2784","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"3c9c18b4eb55c70a200a42832e7f2e48be01e9b7","datavalue":{"value":"https://arxiv.org/abs/1312.1725","type":"string"},"datatype":"url"},"type":"statement","id":"Q424856$1BBA7A98-F5F2-4D4F-924C-BD3532165992","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"1168be5229176990591ce35d87b8107896db4c05","datavalue":{"value":"The author describes an algorithm producing presentations of graph braid groups (the fundamental groups of configuration spaces associated to graphs). The paper also suggests a motion planning algorithm for many particles (robots) moving along a graph avoiding collisions; the complexity of this algorithm is linear in the number of edges and is quadratic in the number of robots. The author also shows that the 2-point braid groups associated to \\textit{light} planar graphs admit presentations where all relations are commutators. A graph \\(G\\) is said to be \\textit{light} if any cycle \\(C\\) of \\(G\\) contains an open edge \\(h\\) such that any cycle of \\(G-\\bar h\\) is disjoint from \\(C\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q424856$018D6509-9712-4A22-A406-4ED3A2332227","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"5f5206f46c6ca666840f8b4128198bef996fcacb","datavalue":{"value":"57M05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q424856$585ED17F-B9ED-4D16-A718-683AFE2F8FC6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"00c103224d34af523e7fce2ff3e40dd19709f84f","datavalue":{"value":"20F36","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q424856$D8364F13-B427-41BE-8C85-29D5A71DC5DE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"74e7832a915a62c417a3bf8c026eff5989fd94d3","datavalue":{"value":"05C25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q424856$A97D2C00-3D75-4CF6-BC2F-7953D6E06606","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"54619a188e2fef445f43361143b357d4aae6f072","datavalue":{"value":"55R80","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q424856$AAB61F0F-BB59-481E-8D76-F76F79A5430E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"3c9759ba1beabf7a5237e2e05cc9f021be9a23e5","datavalue":{"value":"70B15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q424856$42023CF4-EAA9-4139-A507-A623FFFA2A74","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"15ea9b09fbfd690056ed7c63f44b6185fbeb792f","datavalue":{"value":"70Q05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q424856$927D7E47-2417-46F3-9614-FE7E0A8DEC46","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a94d5bf6eab7bddc9c7abbdf41796f52c9b87335","datavalue":{"value":"93C85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q424856$D6FE21E1-1245-4F73-8583-323F17821DDA","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"f60066c94de683c58321cb7f326972d153cadc10","datavalue":{"value":"6043100","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q424856$C587A83E-70F4-4FEE-A96B-C4C8999531A5","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"dc3502ae89578185620df0a3439589df4c734827","datavalue":{"value":"braid group","type":"string"},"datatype":"string"},"type":"statement","id":"Q424856$86C4E348-08C7-4284-8888-1CEA8DD91B26","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c49b422dcd4b40d359c57f953a77f46d8e6bab97","datavalue":{"value":"motion planning algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q424856$DB8349BE-8A09-46F8-BFA0-E06E7E21C89E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cbda80faf7c66fe809412afa8394210863f0c0a9","datavalue":{"value":"configuration space","type":"string"},"datatype":"string"},"type":"statement","id":"Q424856$606B4973-429E-483F-BAC9-CE671EE5603E","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"b6ccb27ab412f910132a93d7daff3155266e861e","datavalue":{"value":{"entity-type":"item","numeric-id":242473,"id":"Q242473"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q424856$DEB82EA1-8670-44A4-A42C-E17B83CA04E7","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":"Q424856$ACA92204-B70D-4A22-AAF7-2C36BA1A431E","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"02cdd276d0bda453972db37bf8d473f974d7b15e","datavalue":{"value":"10.4310/HHA.2012.V14.N1.A8","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q424856$EF656D1A-2104-4AB6-A937-95F3097741AF","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"eadb768f97e9340ca4f5e77ff604ae372afe80f3","datavalue":{"value":{"entity-type":"item","numeric-id":2905097,"id":"Q2905097"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d73648f8a665fcdb4b98d6e2fe0d24379dd70f05","datavalue":{"value":{"amount":"+0.801393449306488","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":"Q424856$D88C5F4C-6A07-4354-9E6C-46AB4603CE1D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"70bcf4131e82a226048e9753bf5265ae77ffb60f","datavalue":{"value":{"entity-type":"item","numeric-id":4529469,"id":"Q4529469"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a4e20177a93d5d53403cc68e22cc078490edb63d","datavalue":{"value":{"amount":"+0.7910756468772888","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":"Q424856$9E62BE2D-1E93-4011-A77E-AFD4D28CDB7A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"192ab4850a9178484bc0da86ecc58c971d63df3b","datavalue":{"value":{"entity-type":"item","numeric-id":1930541,"id":"Q1930541"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"dce2f881a172b9501c5a72df44e467c7dc24c776","datavalue":{"value":{"amount":"+0.7665455937385559","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":"Q424856$1D0E89ED-8335-409A-8925-8D39029B5A47","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5176e351dbc78e66defb074c5988476717e78ff6","datavalue":{"value":{"entity-type":"item","numeric-id":2571377,"id":"Q2571377"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b42f5a3636f4c9c042a4c6db6b4841af29f744c2","datavalue":{"value":{"amount":"+0.7603810429573059","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":"Q424856$69C79854-1BBC-44D1-8275-8B205A51763C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6da37ab829fb6b54342f1344ff99104f9168b9bf","datavalue":{"value":{"entity-type":"item","numeric-id":1323458,"id":"Q1323458"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"61efe98fa9f58272bbb78fabb6e49c053c9dcdc8","datavalue":{"value":{"amount":"+0.760076642036438","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":"Q424856$F5CA22E9-2B1C-43CD-813F-E926126F7CFE","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Computing braid groups of graphs with applications to robot motion planning","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Computing_braid_groups_of_graphs_with_applications_to_robot_motion_planning"}}}}}