{"entities":{"Q2380872":{"pageid":2391615,"ns":120,"title":"Item:Q2380872","lastrevid":74213130,"modified":"2026-04-14T18:59:27Z","type":"item","id":"Q2380872","labels":{"en":{"language":"en","value":"All-shortest-path 2-interval routing is NP-complete"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5692043"}},"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":"Q2380872$8DD56277-C8F1-4458-8C0C-C7579BE67549","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"7bd58e2f5624579b2599d4038dfcecb9b1b080a6","datavalue":{"value":{"text":"All-shortest-path 2-interval routing is NP-complete","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2380872$8FFC25EB-F2A9-47D5-A7C7-62FA2E4C608B","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"ce2663acd3236a77fa3a533d9fd79c4a14d40e38","datavalue":{"value":"1215.05192","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2380872$1D81A6E5-DAAE-43AA-A67B-1B472B91307C","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"013b1b5f16d4ee4bfbc1f9c26a3e1249da81040f","datavalue":{"value":{"entity-type":"item","numeric-id":237583,"id":"Q237583"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2380872$F4698CE6-DF34-43D6-844C-94D51FD2D661","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"154f8f77d7a06c84d91f3c08d17a8cf9ea252571","datavalue":{"value":{"entity-type":"item","numeric-id":2380871,"id":"Q2380871"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2380872$F3834B5E-8BDD-46A3-AD81-252B52511782","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"45b30f4f2be32f2ca8775b6f0e6e9580a407fe4f","datavalue":{"value":{"entity-type":"item","numeric-id":644625,"id":"Q644625"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2380872$BB87835F-7AF4-4208-B0BE-AF1DBFD4CF13","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"e69251ac594e715cd30473d60ecf4960f751c916","datavalue":{"value":{"entity-type":"item","numeric-id":295417,"id":"Q295417"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2380872$D91C5D03-2585-4242-B980-BF559B7B1A3B","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"4583ff7afc41200de2cda3059c167faa7fd9de09","datavalue":{"value":{"time":"+2010-04-12T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2380872$BD2A4916-B09F-4D6D-978F-3CCB3F6CB806","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"749b7137f279a66a306e75e15f613231b281c1c5","datavalue":{"value":"05C85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2380872$182C171A-196F-43B7-91E1-20B6B2CBE142","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"007f7f82691f1d7656215e5be329d57b0bfdf5e7","datavalue":{"value":"94C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2380872$18E3A4B7-EE2B-4DE2-B339-C0F1D48D946C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"8195a9e26c453276e1d31339bf2413392412013d","datavalue":{"value":"68Q17","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2380872$B2F97068-570A-4923-A7B5-075CA0F4F25A","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"cfc6a0c040d69124524f413d221f33999ad1fd27","datavalue":{"value":"5692043","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2380872$F1F98823-76A6-4F6A-81C9-21ED90C8DDF8","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"69ae8eced4b5746917f028f1d44419527ca3c9df","datavalue":{"value":"interval routing schemes","type":"string"},"datatype":"string"},"type":"statement","id":"Q2380872$AFFC1045-DD06-4C17-9B9F-2EAA0B774FE9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b3ff8bc3802e037a73949bd511a5af95815b5cf0","datavalue":{"value":"compact routing","type":"string"},"datatype":"string"},"type":"statement","id":"Q2380872$B10D64B3-37DD-4C45-804A-70E8AF2DE53C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cf1bbad404b660dcc4f7e1f74269a25b269f6b2f","datavalue":{"value":"NP-completeness","type":"string"},"datatype":"string"},"type":"statement","id":"Q2380872$75FA85ED-5BF6-442F-B197-2DA688E5C7E5","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":"Q2380872$46C7E106-97BC-464B-91E3-C76A2ED6F5C0","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"00cd64eac311ed860e31d2fe259a6c0a387ab11c","datavalue":{"value":"https://doi.org/10.1007/s12190-009-0265-2","type":"string"},"datatype":"url"},"type":"statement","id":"Q2380872$59581021-2AD7-4F08-BD62-E3B889CC2170","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"ebe1e8298df73caee47cc14a2f1f579019c8e7ff","datavalue":{"value":"W2090736241","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2380872$ABB405E0-F8A4-4BC0-8D73-36D4B6CF7334","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"06d48f21b86acc37cbf2a178cbf59e7536f03c3b","datavalue":{"value":{"entity-type":"item","numeric-id":3875975,"id":"Q3875975"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2380872$44C46357-7F09-4AA8-B652-F1E827F58406","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"63847ccfe4c7098ed29d701e468ca5ef96ff4ad4","datavalue":{"value":{"entity-type":"item","numeric-id":1853562,"id":"Q1853562"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2380872$2D4CFE05-04B2-4CC1-B45F-F2FE0DC01AD1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7cccea314f88b83bd8984b09b8ffd6056d4a20a8","datavalue":{"value":{"entity-type":"item","numeric-id":5916403,"id":"Q5916403"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2380872$64182029-2C09-49BF-B095-6A4B0E32A950","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a6ed99e4f12d948a815366bf568d151680dafa38","datavalue":{"value":{"entity-type":"item","numeric-id":2744657,"id":"Q2744657"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2380872$E98F0342-1B1E-4655-BDA1-5788058034F9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ed606a3128e43844417dc5e41c6e3931b6df9229","datavalue":{"value":{"entity-type":"item","numeric-id":5361412,"id":"Q5361412"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2380872$2B68BA39-93AD-4FB6-B9D1-34D6B5119197","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b2b7958dc2b7884b86126cf911b9071d9ab73aa9","datavalue":{"value":{"entity-type":"item","numeric-id":4115165,"id":"Q4115165"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2380872$DF548EB1-2A3D-4CA2-BC4F-5E00980EB0F2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1e28ccbc2f71e85a51c369982b6750861b385a44","datavalue":{"value":{"entity-type":"item","numeric-id":1575744,"id":"Q1575744"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2380872$C865AB48-8D74-4142-BCB7-45FED8C65B5C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"aa1121804a3b7fc6501538e7b5ab2db6502e2e42","datavalue":{"value":{"entity-type":"item","numeric-id":1827290,"id":"Q1827290"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2380872$F7AFA4DF-A81B-471F-A70E-7BC15F08EF87","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"abf2a940947b8bdb948c7eaed708bc87573fabbe","datavalue":{"value":{"entity-type":"item","numeric-id":4886687,"id":"Q4886687"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2380872$C574E5B6-2B68-4896-8BD2-28B8891E7C9F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8436a6467ffb057d8b11d18063b5e47b7d550af1","datavalue":{"value":{"entity-type":"item","numeric-id":3220503,"id":"Q3220503"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2380872$71DCC802-D5E1-4189-95AB-831E9B07E8DE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"37c0dc8afdd5bf04f9850c2ee021ce9326f9c977","datavalue":{"value":{"entity-type":"item","numeric-id":3711761,"id":"Q3711761"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2380872$CAD1B905-092E-49EC-A304-A97A31267C36","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3e42b706edb0c243c49ab6832b8e2a10bbbd3bb1","datavalue":{"value":{"entity-type":"item","numeric-id":3798237,"id":"Q3798237"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2380872$24ED603E-CC96-4B03-B2EA-5661A70BDBF8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"055c27e7518703b43c41d62dfcc2ed21f6890aad","datavalue":{"value":{"entity-type":"item","numeric-id":2457012,"id":"Q2457012"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2380872$71A74327-C637-48A7-BFFC-83BCA1C605EF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"719d7ff0d69583120eb590bc1b861211d985ce15","datavalue":{"value":{"entity-type":"item","numeric-id":5315234,"id":"Q5315234"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2380872$75A190FE-9E82-4E30-A10B-CBC533CCC0D3","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"f95fef56f0801d760a89a9c280d8dbd65188deb9","datavalue":{"value":"10.1007/S12190-009-0265-2","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2380872$FE4EA3E7-54DE-49B7-B38C-44B36D134D29","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f79a005cbd98dab2f5ebd77a910df96273c60216","datavalue":{"value":{"entity-type":"item","numeric-id":5315234,"id":"Q5315234"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f1622634262957bbcd40a5381919ad30d822295b","datavalue":{"value":{"amount":"+0.95592254","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":"Q2380872$B0D28A2E-0969-4A18-A798-75A02FE58A22","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f8974fcd9788c0d12ca68ccc48dc20d2c9bb00fe","datavalue":{"value":{"entity-type":"item","numeric-id":4536937,"id":"Q4536937"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"886326bef568cf85ab963f656a48a6adf74f0c42","datavalue":{"value":{"amount":"+0.87389094","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":"Q2380872$2BFEA68C-71D3-4D7B-99B6-859052AFD046","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f30d3f3f95b95f498d7e546a2ebf62bd2d54ab42","datavalue":{"value":{"entity-type":"item","numeric-id":1575668,"id":"Q1575668"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"886326bef568cf85ab963f656a48a6adf74f0c42","datavalue":{"value":{"amount":"+0.87389094","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":"Q2380872$CD80C351-CFC3-4862-A683-32B058D353B2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0abf74fcbb72e9c9d5debe06d5f3b48b80369172","datavalue":{"value":{"entity-type":"item","numeric-id":2465642,"id":"Q2465642"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"bcb1eb0bc137de3986df9289e6fa9746f11accaf","datavalue":{"value":{"amount":"+0.87220955","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":"Q2380872$A75C0392-490C-408F-8755-1DD916592BBB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2e4053d646187910e75a1fc6528d627fa784772d","datavalue":{"value":{"entity-type":"item","numeric-id":4887753,"id":"Q4887753"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"829efd823dd499e57145ddec7251a0cc79c35d94","datavalue":{"value":{"amount":"+0.87113357","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":"Q2380872$44966565-7730-40B0-BBFE-6EB6C050DBD9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"17dcf0f66ff73915a5873f795742c98a4bbfb28e","datavalue":{"value":{"entity-type":"item","numeric-id":2784477,"id":"Q2784477"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1332f38ad74e676e9ca94ce77f4285b130984ba7","datavalue":{"value":{"amount":"+0.86771137","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":"Q2380872$577EAD8E-D248-4553-AC6D-0C9D5A72524A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"bb49401ea55bb4e0f4465edc78c3cdeeb548e509","datavalue":{"value":{"entity-type":"item","numeric-id":3989542,"id":"Q3989542"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b0d6af0d123d5893db0411209c413240f9d81477","datavalue":{"value":{"amount":"+0.85675484","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":"Q2380872$80D00C20-102D-4457-8047-CC228092E7E1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e9a3dbce58063c69d85ba697dc8b2f912eea1246","datavalue":{"value":{"entity-type":"item","numeric-id":1377673,"id":"Q1377673"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c966031d5732c9e5d7d55c2ecec75169bf3e12f4","datavalue":{"value":{"amount":"+0.8564984","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":"Q2380872$87A3C12C-D952-47C7-80F9-1B015AC71E09","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ff27147f073b4a33b12ead529fc96a7f3d6a5e04","datavalue":{"value":{"entity-type":"item","numeric-id":2744657,"id":"Q2744657"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e5aab6889a908a759a2736ef9043c89b179b8e79","datavalue":{"value":{"amount":"+0.8540795","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":"Q2380872$886A1893-7775-40B9-9168-F89C70C806C4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8cb93b3de681e2edc9505bd89030e6a24a962f75","datavalue":{"value":{"entity-type":"item","numeric-id":4209271,"id":"Q4209271"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7ee6ae03d4bf536acf69ae209118d0a194c02cb5","datavalue":{"value":{"amount":"+0.85068774","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":"Q2380872$E2EB7B77-85E8-4B21-AE4C-DD5356F4C9DD","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"All-shortest-path 2-interval routing is NP-complete","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/All-shortest-path_2-interval_routing_is_NP-complete"}}}}}