{"entities":{"Q1183497":{"pageid":1194246,"ns":120,"title":"Item:Q1183497","lastrevid":47057449,"modified":"2025-12-31T13:13:27Z","type":"item","id":"Q1183497","labels":{"en":{"language":"en","value":"Shortest path and closure algorithms for banded matrices"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 33333"}},"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":"Q1183497$2DD1DCDC-BC25-40D7-B2A5-3CF5ECAEF31F","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"2700b2cbd265b16eea2a59cc536f2db92e87b3f1","datavalue":{"value":{"text":"Shortest path and closure algorithms for banded matrices","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1183497$A0809B5E-4222-40F9-83D2-85BF1DFF1B00","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"6da7a63e0d016438b988351456ce58e6895b9e82","datavalue":{"value":"0753.05001","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1183497$8A2D5371-FC80-44BA-B381-85C354E0AB7F","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"93c05bd7f1fa2ea7172c3ed64b908eb27811517a","datavalue":{"value":"10.1016/0020-0190(91)90200-2","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1183497$2B4BCFB2-5CBF-4FE1-BBE5-545E3EEED9CA","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"bbe95f4bec9c420ac8c620638c1022332a927287","datavalue":{"value":{"entity-type":"item","numeric-id":912790,"id":"Q912790"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1183497$29CDA678-3630-4EAF-8BAC-96E376168008","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"2058de3b767af2370597404b4e9c50f75c0be3dc","datavalue":{"value":{"entity-type":"item","numeric-id":294678,"id":"Q294678"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1183497$9F10F932-9557-4CFC-9E8B-85497019FB75","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"492d77041c70e52462e7f0cc75ddf34235527e70","datavalue":{"value":{"entity-type":"item","numeric-id":294679,"id":"Q294679"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1183497$EB776B4F-073D-4C4B-B3FA-3B424790378D","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":"Q1183497$7025F2BD-BE25-4983-B433-EDBB6F5C0CAE","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"120787504bea9565def539fb4bfb19084956028b","datavalue":{"value":{"time":"+1992-06-28T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1183497$35151300-A384-4587-AE86-292B7B3F7515","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"357064655336f357220cc9864ebd4e8066b09792","datavalue":{"value":"The proposed algorithm is a modification/extension of Floyd's: it finds all shortest paths in a \\(n\\times n\\) distance matrix, viewed as a (weighted finite) directed (simple) graph, and has improved order \\(O(nb^ 2)\\) for time complexity, compared to Floyd's \\(O(n^ 2)\\); \\(b\\) is the bandwidth. (Also described in a report of Monash University 1989.) Applications mentioned as possible are to other closure problems in OR, with linear inequalities, other all-pair shortest path problems in networks. Negative distances are permitted, whereby a negative cycle is detected in \\(O(nb^ 2)\\) time. Description of Floyd's is placed at the front. The idea is to preprocess the matrix for finding the limiting elements of the band and restrict Floyd's, so that it stays between these limits. For achieving the smaller order, the input must be in ``compressed'' format, e.g. as adjacency lists of the underlying graph. The actual execution uses the same ``elementary'' operations as Floyd's, mainly \\(f_{ik}=\\min(x,y+z)\\), but about five times as much of the latter ones, so it may be faster at least for \\(b<n/\\sqrt 5\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q1183497$D4E8517F-D902-4444-8C30-363F5630B04D","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"6a81378181b4cb5653e2ae093278092e94c70ad6","datavalue":{"value":{"entity-type":"item","numeric-id":587221,"id":"Q587221"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1183497$5BD23CCD-CB53-4DDF-9E69-FABD40F046FD","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"2f9920e258389d79a7ef76ef96a77d2e9cc60267","datavalue":{"value":"05-04","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1183497$727C7431-56A4-4856-8F82-1D292CB9469D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"f3a5e47548ef139717b317f83801cfef606a623d","datavalue":{"value":"05C38","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1183497$CFC75402-F742-4CA3-8F28-2E8C42FBED98","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"749b7137f279a66a306e75e15f613231b281c1c5","datavalue":{"value":"05C85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1183497$EEBCB7EC-74D6-4D2C-AD1D-7A24E7B1ED8C","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"b4a94e565aeff11828e641f76dde7e84d0f7b7b4","datavalue":{"value":"33333","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1183497$9B5EC914-CF85-4C1E-8E30-1C577890112E","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f85e9f2721221f48af2e899508349c71e3faa29f","datavalue":{"value":"shortest path","type":"string"},"datatype":"string"},"type":"statement","id":"Q1183497$EE6CEEF2-1973-4929-86DA-AFC2524F12E9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a15b7384e4d5bbd6db6a7be8940695f9cc9698cc","datavalue":{"value":"closure algorithms","type":"string"},"datatype":"string"},"type":"statement","id":"Q1183497$80D1D107-9F28-40FA-9968-BFF7C841678A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0ba3c10466b5c70d48692c6ca542c42edc57df9e","datavalue":{"value":"banded matrices","type":"string"},"datatype":"string"},"type":"statement","id":"Q1183497$E4264575-5991-467B-8823-BBC7BAB5A141","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6e1d913c1c10656b72dc592cbc190ffdfad74d8c","datavalue":{"value":"negative cycles","type":"string"},"datatype":"string"},"type":"statement","id":"Q1183497$5329E208-B0C1-41A3-AFA6-41A062DF4646","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cdac047555efcc874baaab244a1a2a790aeba0bd","datavalue":{"value":"band width","type":"string"},"datatype":"string"},"type":"statement","id":"Q1183497$340F5418-A1F1-4292-8B2D-04C03FE3BD40","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"052bc1006118b062704c1040bb454204873886d9","datavalue":{"value":"Negative distances","type":"string"},"datatype":"string"},"type":"statement","id":"Q1183497$89AB69D9-6C43-4CF1-98E2-C65698E7334A","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"d5a5c5f3874fb0aea7f351cc4ba084a45e76a5dd","datavalue":{"value":"Q62654291","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1183497$A038D01C-B0D4-4F3D-9DF7-7CDE1F0EDFA2","rank":"normal"}],"P1463":[{"mainsnak":{"snaktype":"value","property":"P1463","hash":"1412ceb6c71a23f10e8f7e008bf034264afa1496","datavalue":{"value":{"entity-type":"item","numeric-id":41444,"id":"Q41444"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1183497$4ED27A0E-D266-4E52-9BFB-59006F0EA792","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":"Q1183497$905A6664-1351-4AEE-A42A-57182E250C29","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"b0e52a927ba942fdb7c79f8137ecaf22c66ff911","datavalue":{"value":"https://doi.org/10.1016/0020-0190(91)90200-2","type":"string"},"datatype":"url"},"type":"statement","id":"Q1183497$56076142-5195-45E0-B25B-66468C4F0782","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"3684cc8c74dd5f2c3cd649e5fa8cd075f1aa1775","datavalue":{"value":"W2026630113","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1183497$7E0B4EC3-0B39-4733-9CCE-E0678D8996D5","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"fdce5759a201a1d9fb5fb872a19ea91a8cd8b77f","datavalue":{"value":{"entity-type":"item","numeric-id":1183497,"id":"Q1183497"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1183497$71184BB5-A502-4C3B-9A96-07A6E5F0DA17","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2b989f45b85fa44137ad22092706b6102fd241bf","datavalue":{"value":{"entity-type":"item","numeric-id":78129,"id":"Q78129"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1183497$AA76C8D2-2FDC-43AF-AD78-3BBD24603860","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7fd299e4da24e1350ea30efc3b49e47bd3f214c5","datavalue":{"value":{"entity-type":"item","numeric-id":5590541,"id":"Q5590541"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1183497$3A177190-F077-42ED-9F9E-199F5918A126","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a7d74c7d0c13db79ff0b1db305b9010888ac0842","datavalue":{"value":{"entity-type":"item","numeric-id":3329512,"id":"Q3329512"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1183497$6DA94218-0D88-4CE7-A9E7-BBAC304FF78E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a6315d9cda93162c2aba33a1d3e5ec00f12fd74a","datavalue":{"value":{"entity-type":"item","numeric-id":5729523,"id":"Q5729523"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1183497$7AEB885D-995C-4760-A2F2-58CB74992B4C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9fcaed6b4ca29e8677e09c74fa22e3a8938d2ab6","datavalue":{"value":{"entity-type":"item","numeric-id":5645229,"id":"Q5645229"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1183497$F73EB4FA-8ED9-4BDA-B0D6-EA72411D142A","rank":"normal"}],"P1635":[{"mainsnak":{"snaktype":"value","property":"P1635","hash":"d91b32f43f09beae1d5daffc1585c16a191ff38d","datavalue":{"value":"journals/ipl/AllisonDY91","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1183497$4AF3DCA6-6CB2-4C91-964D-A9CDDDD508D4","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"01371b784b157d7521fee86d2243fb9c0023fc47","datavalue":{"value":{"entity-type":"item","numeric-id":875428,"id":"Q875428"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"eaa1255893e7ab98dba0356272d146a3ccdbc2bc","datavalue":{"value":{"amount":"+0.7796732187271118","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":"Q1183497$AA51F4ED-CD05-416A-A95C-C10D97418B6E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f555756ad3be09de88275409b13dd8a37bfe88a3","datavalue":{"value":{"entity-type":"item","numeric-id":4694733,"id":"Q4694733"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a3942b6c89055d26fe1a9c133675479a2b140b0d","datavalue":{"value":{"amount":"+0.7743682265281677","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":"Q1183497$C16BF552-51D6-48BF-8237-7F249E67E86A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f396416e1f950ddba80b182de2aab91b81f668e0","datavalue":{"value":{"entity-type":"item","numeric-id":5463439,"id":"Q5463439"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"bf40dc2574f632bf3e4c47770c13f9da79329411","datavalue":{"value":{"amount":"+0.7710967659950256","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":"Q1183497$FAFCCF37-62D6-4942-9F5E-4A25722D3626","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"bd532fad90b8ec7f00e795fa4c059bd2edbc6830","datavalue":{"value":{"entity-type":"item","numeric-id":2722000,"id":"Q2722000"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0590e5682fc37108e4eb893abf04801f3c8a646f","datavalue":{"value":{"amount":"+0.769338071346283","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":"Q1183497$29390608-A96C-49FB-80C8-58E7B6E19D00","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d3f6ce5ff627fd636dbbb379edbc6ae64cd9bfed","datavalue":{"value":{"entity-type":"item","numeric-id":5929143,"id":"Q5929143"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4ebf5c8d328e6454a9b5c437f911968c9891e069","datavalue":{"value":{"amount":"+0.7682086825370789","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":"Q1183497$3DF06320-0B33-4430-A0D1-E42BEFB22906","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1183497","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1183497"}}}}}