{"entities":{"Q1070825":{"pageid":1081577,"ns":120,"title":"Item:Q1070825","lastrevid":66782391,"modified":"2026-04-12T12:50:00Z","type":"item","id":"Q1070825","labels":{"en":{"language":"en","value":"Efficient implementation of a shifting algorithm"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 3938582"}},"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":"Q1070825$21DE561F-8E43-4233-8A8C-EF637449D4D0","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"373f8b4e1225dbb26023c3f79221241101ba5b6f","datavalue":{"value":{"text":"Efficient implementation of a shifting algorithm","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1070825$CC802316-EC5A-47FC-8B34-538456563BA6","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"59e7e618325e674929c7e4a32794f39a7740bf6d","datavalue":{"value":"0585.68067","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1070825$AF51663A-404B-4665-90DA-D7B562643B10","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"d561b92e58c13a51dc88029a297b9ea0cb47f87c","datavalue":{"value":"10.1016/0166-218X(85)90041-1","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1070825$C627D71D-4F20-4AD4-9F49-1ADEAC5EE9F6","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"526220134f5947b7febab96d61df622608889cb7","datavalue":{"value":{"entity-type":"item","numeric-id":686519,"id":"Q686519"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1070825$468FF57A-E5C3-4F3B-953A-3FF0BAFC70E6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"34b7d653f435d2f694c81d8e0cb65871405ebb3d","datavalue":{"value":{"entity-type":"item","numeric-id":690246,"id":"Q690246"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1070825$FB0EEC37-7B19-43DB-9413-FC09C94B90AF","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"087f55844cc920aae060b09644168bf17b022e1a","datavalue":{"value":{"entity-type":"item","numeric-id":96294,"id":"Q96294"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1070825$173C6108-9198-4897-9769-9F3230F7B936","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"3c94df5c9af0ede578c52141befd29044de13172","datavalue":{"value":{"time":"+1985-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":"Q1070825$F9E92561-D83F-4E23-B97B-20A56A913E8C","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"3632b193cf6ef4eba16a212ccd7074d7f020c5e4","datavalue":{"value":"Let T be an undirected node-weighted tree. The \\(\\min\\)-max-(k\\(+1)\\)- partition problem is to remove k edges of T such that \\(\\max_{1\\leq i\\leq k+1}w(T_ i)\\) is minimized, where the \\(T_ i\\) are the remaining connected components of T and where \\(w(T_ i)\\) is the sum of the node- weights of \\(T_ i\\). An implementation of time complexity \\(O(Rk(k+\\log d)+n)\\) of the shifting algorithm given in the paper of \\textit{R. I. Becker}, \\textit{Y. Perl} and \\textit{S. R. Schach} in J. Assoc. Comput. Mach. 29, 58-67 (1982; Zbl 0477.68066) is described. Here r is the radius of T, and d is the maximum degree of any vertex in T.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1070825$41047800-BD97-4CB0-9347-C8DA85AD48E8","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1070825$0F98579D-A90F-49E5-B8AA-945EC2CBC946","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"d5da87a72c21717089feda882f568938059a9d84","datavalue":{"value":"05C05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1070825$AD3B74CA-BF77-4329-B446-8B936CE9533A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1070825$782C2363-94A5-4CA6-B024-690C3F289A1A","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"3e22aea2bdbcfd0a6530aac0c3ebc3ef12c15118","datavalue":{"value":"3938582","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1070825$708863BE-6712-4179-8CEB-C0A33F8D395B","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"06c419822e027da1fe08bb363fb4dda4d864ec8d","datavalue":{"value":"min-max partitioning","type":"string"},"datatype":"string"},"type":"statement","id":"Q1070825$093F8ABB-C8E7-4E37-87DE-A83DD8642E0D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b0ef7315e70880a4908bc221e4019c4dae8e4003","datavalue":{"value":"tree partitioning","type":"string"},"datatype":"string"},"type":"statement","id":"Q1070825$70147293-56EB-4216-A886-5140DFA69A80","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"29e1b597045d3e5749299d055158f389a8b5eff4","datavalue":{"value":"undirected node-weighted tree","type":"string"},"datatype":"string"},"type":"statement","id":"Q1070825$BBFC57D1-8631-4464-8F0C-E35AC015C5E8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"53064f6609fb5177611c085d6f78e739c7e3f7f6","datavalue":{"value":"time complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q1070825$E133CAEA-F2D9-4CC0-921A-90C7EDCC8491","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"c666ac2d78f9f2d8ad99cfc32edd5f33e6fa3ff8","datavalue":{"value":{"entity-type":"item","numeric-id":287186,"id":"Q287186"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1070825$6126550A-5583-4B9B-AD36-76B678105491","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":"Q1070825$B7B67904-247C-4FDB-BEF4-345A15D8F941","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"5cc924856c00da163720e9b0839658d921b72bc3","datavalue":{"value":{"entity-type":"item","numeric-id":686520,"id":"Q686520"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1070825$E6E7D453-F82E-4B18-B3F9-63B56D91A85B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8dc4a0c974c8d69e00fdbe82fbf3a207c65e56f0","datavalue":{"value":{"entity-type":"item","numeric-id":3933759,"id":"Q3933759"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1070825$90BD8368-B3E1-4633-90AC-AEF5433FC4F1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7d844b310b91902135642d810ef561d41a2da626","datavalue":{"value":{"entity-type":"item","numeric-id":3667953,"id":"Q3667953"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1070825$1019A53D-4876-4680-B3AF-4388197AE606","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"19ee47c47c223cfb9ec56146022c30ef75f454f0","datavalue":{"value":{"entity-type":"item","numeric-id":3870691,"id":"Q3870691"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1070825$8C4157A3-D8BB-4149-A992-F786E8B8B135","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3a40f026b0a9075e24f8b393e8259ad22df83c3e","datavalue":{"value":{"entity-type":"item","numeric-id":4116058,"id":"Q4116058"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1070825$8034199B-D2D7-48B3-8DBC-D142E5C252E9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5a42ee58f9827e5374e9c19ea4c070afa6055eec","datavalue":{"value":{"entity-type":"item","numeric-id":3902511,"id":"Q3902511"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1070825$039469B8-17F8-4750-8B44-AB646D8C558A","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"ccd613441b4ad59e35050905a0deb4f91a075b0d","datavalue":{"value":"https://doi.org/10.1016/0166-218x(85)90041-1","type":"string"},"datatype":"url"},"type":"statement","id":"Q1070825$5CD3D6AF-F8E2-49ED-B964-B2086471F5C4","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"80907c8bcf93984c2e49d99693321fc398c4123b","datavalue":{"value":"W4213040960","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1070825$F56D3C78-F9D6-43AB-B4AC-6FE6F98833DF","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f101b99620db61e5b8e32d3c2c05615678cad23f","datavalue":{"value":{"entity-type":"item","numeric-id":686520,"id":"Q686520"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ddd9de16eda7b4948d457302a0e58d1c938c3632","datavalue":{"value":{"amount":"+0.8357347249984741","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":"Q1070825$8FB86E76-71D5-409F-86D3-9A55D810082F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0c89bdd39abf4bb48fa6bc12851496a4a6df7b31","datavalue":{"value":{"entity-type":"item","numeric-id":3511413,"id":"Q3511413"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a466d1a3b8ec9ffda4f38d7464e676ea5ed2d2c1","datavalue":{"value":{"amount":"+0.8352183699607849","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":"Q1070825$D7CD07CD-C469-472B-BC3B-3AAD4D8C13B6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fe5bc304c9926749dee01eb61d32c506ddcedb8b","datavalue":{"value":{"entity-type":"item","numeric-id":1900135,"id":"Q1900135"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2d8fd26dc1dc0c7c4824e0ae3c4b64c733a16d3b","datavalue":{"value":{"amount":"+0.8191215991973877","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":"Q1070825$829F5E16-1B71-49FD-B3A2-1C1D5938EFF3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"34099a75f1a2977224c9c0c8a50bf9a34d6a58e8","datavalue":{"value":{"entity-type":"item","numeric-id":3334089,"id":"Q3334089"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ff3c2201518d5f55b29e1e191af8b3226978d7ce","datavalue":{"value":{"amount":"+0.7924129366874695","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":"Q1070825$0F96860F-C28A-4D73-81EC-008C3C01C0A1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1855755d5c762baf614ca8aaa7b7aea3b7c09873","datavalue":{"value":{"entity-type":"item","numeric-id":3339302,"id":"Q3339302"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"be488d1acc187133129ff12c5f556b554c5d3da6","datavalue":{"value":{"amount":"+0.7904563546180725","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":"Q1070825$8CFD0ABD-FCD2-4A30-88C1-216FFF3CDA52","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Efficient implementation of a shifting algorithm","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Efficient_implementation_of_a_shifting_algorithm"}}}}}