{"entities":{"Q1791343":{"pageid":1802085,"ns":120,"title":"Item:Q1791343","lastrevid":69367125,"modified":"2026-04-13T06:31:35Z","type":"item","id":"Q1791343","labels":{"en":{"language":"en","value":"Algorithms for the shortest path improvement problems under unit Hamming distance"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6950904"}},"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":"Q1791343$5CD82899-279F-4840-B773-2BED5B39D9FD","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"d1ae14c8a093ffef61120b700eee08bbf7bf266d","datavalue":{"value":{"text":"Algorithms for the shortest path improvement problems under unit Hamming distance","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1791343$CF545F3C-AF11-4EEE-9545-19F3AAB2746C","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"5fd879632cd5005baff78b9778007fd1a8139251","datavalue":{"value":"1397.90389","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1791343$C74530F4-3D26-4995-B6BD-ECBB98827534","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"21436f17f9c032013fe9bdb654afee564cbfbaea","datavalue":{"value":"10.1155/2013/847317","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1791343$C6CE57F9-63A3-46FC-9F57-45EF4F4868AA","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"aff486f6d8655c442ea97c3a145fa79088f4d1c6","datavalue":{"value":{"entity-type":"item","numeric-id":1791342,"id":"Q1791342"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1791343$67AA5AED-B63E-4800-87D1-010A6E3F7865","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"2bf3bbba90607101707f364e177b1045812ab266","datavalue":{"value":{"entity-type":"item","numeric-id":445337,"id":"Q445337"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1791343$9CE2D942-A33F-43DB-A636-369319484DE5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"7f4bbf4492643d73050f4fbfac344ea192aac544","datavalue":{"value":{"entity-type":"item","numeric-id":1670105,"id":"Q1670105"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1791343$281DA700-7B9E-4BC2-BE1E-CF550B10E42D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"415f0c948ec4fdf7372055201c8e10d4f0f3066b","datavalue":{"value":{"entity-type":"item","numeric-id":430265,"id":"Q430265"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1791343$3DF56BE8-AD51-4C5F-B2F9-BC8CD57FD9D1","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"bb299feb2b87699ac8beef494c52fd2765eaf609","datavalue":{"value":{"entity-type":"item","numeric-id":118601,"id":"Q118601"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1791343$6A4CBA1D-C8FB-48C4-AFD0-1D382DB3DF0C","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"9a9a21eafa993b72759052108b216b22ca406dd9","datavalue":{"value":{"time":"+2018-10-10T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1791343$B5EFBB0A-5407-4071-A00E-02C87BE9788C","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"e59e9136d960a3dfc3bbaef59ceeac61802b1777","datavalue":{"value":"Summary: In a shortest path improvement problem under unit Hamming distance (denoted by SPIUH), an edge weighted graph with a set of source-terminal pairs is given; we need to modify the lengths of edges by a minimum cost under unit Hamming distance such that the modified distances of the shortest paths are upper bounded by given values. The SPIUH problem on arborescent network is formulated as a 0-1 integer programming model. Some strongly polynomial time algorithms are designed for the problems on some special arborescent networks. Firstly, two greedy algorithms are proposed for problems on chain networks and special star-tree networks, respectively. Secondly, a strongly polynomial time algorithm is presented for the problem with a single source and constrained paths. Finally, a heuristic algorithm and its computational experiments are given for the SPIUH problem on general graphs.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1791343$736AE1A1-860C-4EC8-A16B-6FD0EEE89F93","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"d2d4f4e28fa9ca38421c473fcb6ba728a44de59a","datavalue":{"value":"90C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1791343$830C1F0C-8501-4AD8-92FB-36D232F222FB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"8195a9e26c453276e1d31339bf2413392412013d","datavalue":{"value":"68Q17","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1791343$F860413E-2204-4C20-B6C8-E6EF667BFD37","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"f7f9c96debf4838ca257cb5cf8b5834c8c33a950","datavalue":{"value":"6950904","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1791343$8251BF1A-D3BF-45D4-B282-0482E4D6F0BC","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"c41060b856e89eb33f6c0e0e73d8edaf4a4a95c0","datavalue":{"value":"Q59004819","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1791343$252C5AE8-C609-4A74-A667-E4D3C100B589","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":"Q1791343$38C6D011-521B-4E22-8A49-814E33F31D17","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"0804350f554fdc720fe8e21aca174163dab03d59","datavalue":{"value":"https://doi.org/10.1155/2013/847317","type":"string"},"datatype":"url"},"type":"statement","id":"Q1791343$C3A25434-73C1-4C0F-9022-0353334C510C","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"a8f4373611020134556075dbd6782d953686a36a","datavalue":{"value":"W2166042729","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1791343$C9C4A9B6-E441-4F7A-A9C6-FA8468D2E680","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"295bececf544d76d6acd07fb44d6e89b0c9a4719","datavalue":{"value":{"entity-type":"item","numeric-id":2385466,"id":"Q2385466"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"14ef4018e5f15d29b47c0b9a265914b9051ab1e6","datavalue":{"value":{"amount":"+0.9125909209251404","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":"Q1791343$435C9C86-AF80-4242-9108-426E6202B012","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ae5e8f58938d429d323cecb9250d948864cfff4f","datavalue":{"value":{"entity-type":"item","numeric-id":1670106,"id":"Q1670106"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"12c35ce7579ef9ce282a91bb11c2046c567969c2","datavalue":{"value":{"amount":"+0.8896917104721069","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":"Q1791343$BCC4D09F-5AC5-4919-8E77-75A205119E8F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3d9f148aa9d96e3b4aae25709921e1faf7cd3c2c","datavalue":{"value":{"entity-type":"item","numeric-id":5322840,"id":"Q5322840"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"fd3ffc9b8457e87d7a36a5d4bcdecf2b397f9bf6","datavalue":{"value":{"amount":"+0.8713074922561646","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":"Q1791343$DDE6DDF2-983B-4C58-B3FC-C9ECF3D6826C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"effb24b029d53c2810d68d645c23b686f1cd7e08","datavalue":{"value":{"entity-type":"item","numeric-id":3644697,"id":"Q3644697"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f879d99d50f6ba928b94929bae826b8c633ce0a8","datavalue":{"value":{"amount":"+0.848961591720581","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":"Q1791343$DDFEF203-FFEC-4AF2-B37C-ABBD45A4A9CE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"10273150ce7713c31b7aa7aa5d5bdb3f66a7b530","datavalue":{"value":{"entity-type":"item","numeric-id":3466912,"id":"Q3466912"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4c12092fcdba294a72e433ebeeae95b529c4c125","datavalue":{"value":{"amount":"+0.8300986289978027","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":"Q1791343$FC670C2A-D01F-43F2-813E-6FDFBD70CCCC","rank":"normal"}],"P163":[{"mainsnak":{"snaktype":"value","property":"P163","hash":"45fcd4163b5f33e6e8c784f5522d7246c0a1a61e","datavalue":{"value":{"entity-type":"item","numeric-id":57056,"id":"Q57056"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1791343$1CF07958-36FC-4C27-8B8C-B75734E57703","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Algorithms for the shortest path improvement problems under unit Hamming distance","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Algorithms_for_the_shortest_path_improvement_problems_under_unit_Hamming_distance"}}}}}