{"entities":{"Q2369383":{"pageid":2380126,"ns":120,"title":"Item:Q2369383","lastrevid":49827379,"modified":"2026-01-11T02:43:28Z","type":"item","id":"Q2369383","labels":{"en":{"language":"en","value":"The constrained shortest path problem: algorithmic approaches and an algebraic study with generalization"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5022245"}},"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":"Q2369383$149EC732-812F-4984-ACB3-63487828317E","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"3130c8c27edced70e5006d2c368027aece7c1e8d","datavalue":{"value":{"text":"The constrained shortest path problem: algorithmic approaches and an algebraic study with generalization","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2369383$88097DD2-A507-4B10-9607-9921A3BB74A0","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"3fad4a2a1409d0f1aa49ba3e663660116be778d4","datavalue":{"value":"1136.90034","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2369383$E6276C3E-3449-4AE6-BCC1-787D57B20F41","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"4a65dc856d9e974ec3b1f7ffec4ed8899a75c74e","datavalue":{"value":{"entity-type":"item","numeric-id":1870396,"id":"Q1870396"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2369383$AC3129DC-EC13-4038-928E-244C94AF283B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"0c903be731081110bd1be3259fa57b8aea3525ae","datavalue":{"value":{"entity-type":"item","numeric-id":528471,"id":"Q528471"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2369383$85A346E9-C432-4752-A7C4-B147CDE62497","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"0391b7c4dfba8c377da7d81f897d3cf43a7a75ee","datavalue":{"value":{"entity-type":"item","numeric-id":166207,"id":"Q166207"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2369383$16888901-6C08-4ABF-BBB2-CE77D0EF2727","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"68f7cb120594ecd19a2dec3a5faca183ef761964","datavalue":{"value":{"entity-type":"item","numeric-id":714801,"id":"Q714801"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2369383$40547F19-12D3-4ACE-AB44-6FD1B0822BA0","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"03e0344fac3b71001f7d01722f599a45a6c3dae0","datavalue":{"value":{"entity-type":"item","numeric-id":321980,"id":"Q321980"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2369383$CD21A311-1452-4511-8878-C2CCE4876E3A","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"9597f413246d561c71f53debbfd7d35f070a971f","datavalue":{"value":{"time":"+2006-05-09T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2369383$3B513725-095B-4D85-B224-8C57AF9BC29D","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"530bc23b1af637f0392f8bfcf0d75f55a2751df6","datavalue":{"value":"This article presents an overview of algorithms for the constrained shortest path problem. This problem is an \\(NP\\)-hard problem that has been studied extensively in the context of telecommunications and computer science.  The authors start by describing the existing approximation and heuristics algorithms, followed by a precise mathematical formulation of the problem. The next section studies the equivalence of a class of algorithms for the constrained path problem, which is then followed by an algebraic study of the relaxation of the problem.  The fourth and fifth sections of the article investigate binary search type algorithms which are based on algorithms already described earlier, followed by parametric search based algorithms. The article concludes with a section containing simulation results and an extensive list of references.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2369383$26B31084-D9EF-4099-BFCA-97D9148EB2E6","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"58309c80337e7309a39fa8b39c69e1b722b3cd2b","datavalue":{"value":{"entity-type":"item","numeric-id":590170,"id":"Q590170"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2369383$1D6EA7FE-6AB2-474A-8405-E3E107DA9427","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"35cb8465ca85ba26995d54be2905dc35556d665c","datavalue":{"value":"90C27","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2369383$328F5702-F40A-4030-BC26-0277E7D8DD9A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"8d42ae7884b9335550c4d21f090798ce9c56a9bf","datavalue":{"value":"90C59","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2369383$7B514771-0D91-4416-9C9B-B0F7BFEE086B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"5a3bb76dbd41580d9287ece5137de80ddf22202f","datavalue":{"value":"05C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2369383$4880A176-A36E-4965-897E-D71A1A84A160","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"f3a5e47548ef139717b317f83801cfef606a623d","datavalue":{"value":"05C38","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2369383$AFB56E47-53F3-4A05-9B35-2D3ABD724544","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2369383$9024A4A7-9814-4D65-B51D-8D4BA8F1678C","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"f43822c1107c626c29211e78ed8c5ea544381855","datavalue":{"value":"5022245","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2369383$D421C4EC-C545-4C0D-9F87-0D46A700414D","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e4bf50b2fc1360db413033890a52a4cf07a10948","datavalue":{"value":"constrained shortest path problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q2369383$71FC426F-2E88-4C84-9D56-7CD5E2409C3E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"48afb3b071c7136e218c82e61d79bf6875dea359","datavalue":{"value":"discrete optimization","type":"string"},"datatype":"string"},"type":"statement","id":"Q2369383$FE16CCB3-4961-4A06-90DD-650599ADCA03","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":"Q2369383$F62BE166-85B8-4FEF-9CFD-1B463AC65372","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"02cedb0ea2adc3a9e8ece0fd0df4b4402a219580","datavalue":{"value":{"entity-type":"item","numeric-id":3046509,"id":"Q3046509"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b2d227faa6a662b60c9f489ee555eacf8e3d6f7b","datavalue":{"value":{"amount":"+0.7680625915527344","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":"Q2369383$FDB94F03-6B47-4852-BC9B-66CDB1768918","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"abb051464faf07bb6fdd715436d1852760464a0c","datavalue":{"value":{"entity-type":"item","numeric-id":5897843,"id":"Q5897843"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f06e114f7fd19701c16e9313b256a1b625e61732","datavalue":{"value":{"amount":"+0.7613776326179504","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":"Q2369383$DE7839DC-A560-448D-A706-DDAB16D6184F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e0fcc2cde6dd5ebfa451e538f6dbc5a4bf14afa7","datavalue":{"value":{"entity-type":"item","numeric-id":4952841,"id":"Q4952841"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b1404293c63721672976c6112ab203259e82f33a","datavalue":{"value":{"amount":"+0.7464321851730347","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":"Q2369383$A83BAF4D-B03C-4ECF-ACD7-5A5D04E08C1D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d462eea43490b95d3b3dc7a54cd619dd9992defd","datavalue":{"value":{"entity-type":"item","numeric-id":3637313,"id":"Q3637313"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"be2cb1c48166edd198a4ed868424c35fa3a107b1","datavalue":{"value":{"amount":"+0.7417398691177368","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":"Q2369383$615476CD-2B3E-4638-AE22-87CF607D3514","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7e28ac49bd9e1bede858e89424ad815254be29f8","datavalue":{"value":{"entity-type":"item","numeric-id":479240,"id":"Q479240"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"29ac1844e16c14b504838ec65d35ced80ced3448","datavalue":{"value":{"amount":"+0.724367082118988","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":"Q2369383$EEC1479C-598C-45BF-B8BB-709E72CCEF3F","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2369383","badges":[]}}}}}