{"entities":{"Q1101020":{"pageid":1111772,"ns":120,"title":"Item:Q1101020","lastrevid":66721653,"modified":"2026-04-12T12:24:04Z","type":"item","id":"Q1101020","labels":{"en":{"language":"en","value":"A note on the partitioning shortest path algorithm"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4045506"}},"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":"Q1101020$E42511C4-2AD5-41EC-8E09-9AB126C0A094","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"f56ed2d1fcdc20ec38f30ede6e382825bd54beca","datavalue":{"value":{"text":"A note on the partitioning shortest path algorithm","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1101020$F2D5BF59-CB4C-40F4-96BB-4E6B93F9CFA8","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"d76ab0c4aa51a1574ee7a6a4b57917ed87f31d56","datavalue":{"value":"0641.90083","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1101020$022E416E-3B68-430B-90A0-6D051B5125ED","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"c5da2575f64f2cd1cc962465cdf77d44e8245f5b","datavalue":{"value":"10.1016/0167-6377(87)90017-4","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1101020$9179CB7E-7437-47EE-8145-098511D03AB6","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"622b16d11823b1525d20fd74b1b8ed7597116774","datavalue":{"value":{"entity-type":"item","numeric-id":1068006,"id":"Q1068006"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1101020$A58D9434-740A-4EAD-9535-85AE1184DAED","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"f9747a37b0b56aeca2085282046e2737cd5087ca","datavalue":{"value":{"entity-type":"item","numeric-id":96289,"id":"Q96289"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1101020$516BE4EE-ADB9-42AB-8346-576EAE909CED","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"5ae48c61eed19d1e1e1f33f9255d5b329362d064","datavalue":{"value":{"time":"+1987-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":"Q1101020$E882C8E3-433F-4CD1-8384-47FDFE7A87F1","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"7ea783fc3d79043b30c804e8406d641e9c4d9143","datavalue":{"value":"https://ir.cwi.nl/pub/2461","type":"string"},"datatype":"url"},"type":"statement","id":"Q1101020$49BC3CC8-2F20-4F32-A649-6F92566A3774","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"255dae981184153eb97c2e2c06a1bca9edb9e618","datavalue":{"value":"Recently \\textit{F. Glover, D. Klingman} and \\textit{N. Phillips} [Oper. Res. 33, 65-73 (1985; Zbl 0578.90089)] proposed the Partitioning Shortest Path (PSP) algorithm. The PSP algorithm includes as variants most of the known algorithms for the shortest path problem. In a subsequent paper, together with \\textit{R. Schneider} [Manage. Sci. 31, 1106-1128 (1985; Zbl 0609.90103)], they proposed several variants of the PSP and conducted computational tests. Three of the variants were the first polynomially bounded shortest path algorithms to maintain sharp labels as defined by \\textit{D. Shier} and \\textit{C. Witzgall} [J. Res. Nat. Bur. Standards 86, 317-330 (1981)]. Two of these variants had computational complexity \\(O(| N|^ 2| A|)\\), the other \\(O(| N|^ 3)\\). In this note, we add a new step to the PSP algorithm resulting in new variants also scanning from sharp labels and having computational complexity \\(O(| N|^ 3)\\) for two of them and \\(O(| N|^ 2)\\) for the other. This new step also provides a test for the early detection of negative length cycles.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1101020$BBCD0A78-6CD0-414A-943A-9A880A5A5C4C","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"d2d4f4e28fa9ca38421c473fcb6ba728a44de59a","datavalue":{"value":"90C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1101020$1BD6A2D4-8EDD-4DD4-A1CF-5DF4D9411576","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1101020$B634CB4B-87E2-4ECD-8B50-C72D15996CC6","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"1ca68bc1aaef6549c0f7b507bed6fc2e7684ccdb","datavalue":{"value":"4045506","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1101020$0A517E1D-5A1A-486C-BDAB-68FE2233444B","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2d59df9ab53c9a6db676f026966d2ef50f9ae966","datavalue":{"value":"Partitioning Shortest Path","type":"string"},"datatype":"string"},"type":"statement","id":"Q1101020$9D816A97-A0B6-4E4C-AD24-B585D7C14B21","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a777b471cd8ae5fbcf3c69a146e69b749f3965de","datavalue":{"value":"sharp labels","type":"string"},"datatype":"string"},"type":"statement","id":"Q1101020$8071CE24-797B-40DD-99DA-BDBBB3C7488D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c05a19493f461ac328a813bdfefe079e357a35a4","datavalue":{"value":"detection of negative length cycles","type":"string"},"datatype":"string"},"type":"statement","id":"Q1101020$ABC0B113-58BA-48E8-9883-A71D639E3B9E","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":"Q1101020$25F02D27-AC61-480D-B806-C16DC0F157CD","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"e5168c38e3e10f81a4ede6552f73ca290f5d728d","datavalue":{"value":"W2071925433","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1101020$4BBD6D28-9373-4041-ACE8-2B58EF644FA0","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"a43ca27cba6b8cbde68d00987a946f9cde333444","datavalue":{"value":{"entity-type":"item","numeric-id":3844775,"id":"Q3844775"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1101020$16CF83D9-4177-4DAF-B0E4-A0E9DC3F49A6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4823f04d9fb1b5978ca3b1fa99933ee2850940a9","datavalue":{"value":{"entity-type":"item","numeric-id":3049827,"id":"Q3049827"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1101020$F388685B-9363-40E7-8BF7-ADB0745B8C89","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"31e9d2c4e19111a381f5a1d6be206dcb774e280e","datavalue":{"value":{"entity-type":"item","numeric-id":3722287,"id":"Q3722287"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1101020$EA812807-296F-4199-A0B3-D2C2BD99E004","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"170d3842938a1d620c40832ca04450ef4b3918de","datavalue":{"value":{"entity-type":"item","numeric-id":3743140,"id":"Q3743140"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1101020$B4875685-84BD-46B9-8DF0-9F5685DF5C58","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"085f46b3f3ad81bacf48ad53f0c7f1a01aed50d3","datavalue":{"value":{"entity-type":"item","numeric-id":3833887,"id":"Q3833887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1101020$042AD136-E375-4315-BC86-6EED717139B3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2222e6e68cf5e0df7e4e5bfc0d92144d77fdc3b7","datavalue":{"value":{"entity-type":"item","numeric-id":3701214,"id":"Q3701214"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1101020$14C397D2-4BCD-45E5-9F6B-BDA5F0849698","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"49f4e19753fa33f0a8b7b019a0262f56bb60df14","datavalue":{"value":{"entity-type":"item","numeric-id":3750535,"id":"Q3750535"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1101020$73DC7A97-B4D4-4CDA-821D-CC9104CCF3C8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"581d19122944796ba2a16aeb6ce09a7eb0f44718","datavalue":{"value":{"entity-type":"item","numeric-id":4777084,"id":"Q4777084"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1101020$060BAE74-B975-42D1-BA76-4F1167156E2B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"443eaf42e0b578e99595c8551401ff45a5689bd5","datavalue":{"value":{"entity-type":"item","numeric-id":3914450,"id":"Q3914450"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1101020$5AAB4D68-6AD4-4B30-9097-3C3F0DE83361","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a82fbe3cb13dbf5a53e6af006bc914ad88856213","datavalue":{"value":{"entity-type":"item","numeric-id":1074506,"id":"Q1074506"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3239dc055c624455ee473da2080ea2381f95c92f","datavalue":{"value":{"amount":"+0.9481884","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1101020$6633024A-DEF3-48CB-9F23-E194C61A8575","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"dc42573b74a3ac833ba1961f830161f9816df22e","datavalue":{"value":{"entity-type":"item","numeric-id":1900138,"id":"Q1900138"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b6ae8b654cf0e0febf1efa7d75da4cbe831ecfc9","datavalue":{"value":{"amount":"+0.9063215","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1101020$32110363-6EF2-460F-A58D-25EA46B697A9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9ff7cdffa0b05e4b05b366a73550433ac2b2c696","datavalue":{"value":{"entity-type":"item","numeric-id":1803681,"id":"Q1803681"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"49dcb1b61f4c038ac70fe75d0df1b5aace6c83c6","datavalue":{"value":{"amount":"+0.8974166","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1101020$91D36CF1-7870-42E1-AA0C-66E460EB85F6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e8908388d9937941a716c70e7c38520743a64849","datavalue":{"value":{"entity-type":"item","numeric-id":1813975,"id":"Q1813975"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1cde7ba67384b4505a0462d512e0ea02d0ef32db","datavalue":{"value":{"amount":"+0.89215475","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1101020$CDDC6499-307C-48F2-8042-C8DC2E494B8B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2a97bdf9dcc253610046d6546ec129d15df46190","datavalue":{"value":{"entity-type":"item","numeric-id":6113908,"id":"Q6113908"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a8f2f3d0b4ea8e2110cce33e2f48460715c7dbf6","datavalue":{"value":{"amount":"+0.8897056","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1101020$6C9DEF8B-D97B-4A60-9C81-0417180E7F25","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3490c92f0d1b2d4f287fff18cae48ceac4c1e520","datavalue":{"value":{"entity-type":"item","numeric-id":788493,"id":"Q788493"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6805263dc73caae3d81d93bede6d9643d4c4bb4e","datavalue":{"value":{"amount":"+0.88850284","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1101020$13A0D0C2-53C3-42F4-8B4A-85B80F65693D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"38776dc5e7087744d5ea804f791aeafd29a7b85d","datavalue":{"value":{"entity-type":"item","numeric-id":3833887,"id":"Q3833887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b6d875c29c0baa19f67fae192407860e6933736e","datavalue":{"value":{"amount":"+0.8878378","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1101020$1F3A3206-7DF2-4A10-9D7B-7E370D026E2A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d66ab24665bd737b929834a7ebced43c6ad2a31c","datavalue":{"value":{"entity-type":"item","numeric-id":408433,"id":"Q408433"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3d8eabbac8efe727714c49f95cecd976b217f43e","datavalue":{"value":{"amount":"+0.88740563","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1101020$47155B58-6896-48F6-AF06-628507AD8169","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"292e7289db7a649e9ac25339439ecdce265ff071","datavalue":{"value":{"entity-type":"item","numeric-id":3507777,"id":"Q3507777"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"36bd5aff031ae1f77659ffa296724705d4bbad51","datavalue":{"value":{"amount":"+0.88279504","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1101020$BA86CE28-D3D4-49CF-BD9A-B7B2FE0C8061","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"A note on the partitioning shortest path algorithm","badges":[]}}}}}