{"entities":{"Q1814249":{"pageid":1824991,"ns":120,"title":"Item:Q1814249","lastrevid":69029538,"modified":"2026-04-13T03:50:21Z","type":"item","id":"Q1814249","labels":{"en":{"language":"en","value":"A lower bound for the shortest Hamiltonean path in directed graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 10367"}},"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":"Q1814249$4516EBCA-E01E-4FF3-9170-1A420DDA3A36","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"748a16ef2a9c7c1e5032c128c3a55ecb3b2185b3","datavalue":{"value":{"text":"A lower bound for the shortest Hamiltonean path in directed graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1814249$E5ACCBC7-FB14-4127-95D1-E461FFDE038C","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"4df69796238f145eef21cc3d52644ddbabeca4b8","datavalue":{"value":"0744.90091","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1814249$C77ADF8B-19A2-4BA9-9E42-C3DFE089F8AC","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"dc517299c5c2b3ec43b5e093819d367af44406aa","datavalue":{"value":"10.1007/BF01719934","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1814249$AE215545-B2A7-4AC5-8DFD-B6FAB3EA4177","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"924813195b43b8bb74080560a8c18b7cbef85156","datavalue":{"value":{"entity-type":"item","numeric-id":1814248,"id":"Q1814248"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1814249$FADD0440-4E96-4B4E-8802-0FBABA2D8BA5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"b4b382eb2e3a068a862d5096a039ff6b343f2c70","datavalue":{"value":{"entity-type":"item","numeric-id":1096543,"id":"Q1096543"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1814249$F9FBE2DF-9F00-4A0A-ADC8-E6951A48B016","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"9c43b2600d1729fd3bff9a1684164aec83749349","datavalue":{"value":{"entity-type":"item","numeric-id":202828,"id":"Q202828"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1814249$E088CEB2-3C1A-4BC7-87ED-4EBFB1626ECB","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"d3f790682a6be4cc1f3210e15eebe1d6cc5ffbc2","datavalue":{"value":{"time":"+1992-06-25T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1814249$716051DD-0427-46ED-AD63-D40636337961","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"d80e64f7b94ac46f7e6caf6b8fcd2396ab209bc6","datavalue":{"value":"The authors present a Lagrange relaxation of a particular formulation for the shortest Hamiltonian path problem in a directed graph. The relaxation has not the integrality property, but the adequate dual problem defines a lower bound. The dual problem is to find a shortest path with a fixed number of arcs. To solve this one must solve a classical shortest path problem with nonnegative length.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1814249$8909F447-A92B-4268-9E2B-2C85240D1C1A","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"bee1f7445f48f88ea32c13733d6b7ad82b5d2674","datavalue":{"value":{"entity-type":"item","numeric-id":803176,"id":"Q803176"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1814249$F6D48F26-7128-45C5-9866-38C26676285E","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"d2d4f4e28fa9ca38421c473fcb6ba728a44de59a","datavalue":{"value":"90C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1814249$3A485981-D863-4217-BC10-961750A935B7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"3feee98fb6a1a95642ba0c6a16390527874922bf","datavalue":{"value":"90C10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1814249$416313E6-DC1B-4902-9C66-4F5661FF7125","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"28a2562af9ba92a0ffc82bb291618717888effe0","datavalue":{"value":"10367","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1814249$50E7C4CE-F834-4C6B-8D02-0C1ADADB2F76","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b76c57478e7480f586895f73fe9158887c3cad6c","datavalue":{"value":"travelling salesman","type":"string"},"datatype":"string"},"type":"statement","id":"Q1814249$E86F4665-459F-4F7C-9896-E5A4E3B03695","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c1c837f5c1df41e8e68b7f47e36e18225bb517e6","datavalue":{"value":"Lagrange relaxation","type":"string"},"datatype":"string"},"type":"statement","id":"Q1814249$68A0A5D0-3AE7-42BF-A254-3AC1BB58826C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d43b729fd2d515e88ad2e254f326fff730ecb0cd","datavalue":{"value":"shortest Hamiltonian path problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q1814249$CFDC352F-40D1-4BDE-8C72-FA6109F3C27A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6bf023653318cc5b8c727563611596d2cf1a818a","datavalue":{"value":"directed graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1814249$B6332C8C-CD94-480C-8490-0AD1F8169561","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"87b2d83f40d4c014062142e2b6babe456b27d6f1","datavalue":{"value":"Q114233931","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1814249$20D7A252-A8B4-431C-BA0C-BDD723BDAA5C","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":"Q1814249$765F274E-5698-4414-AAD4-EC1E76266834","rank":"normal"}],"P223":[{"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":"Q1814249$D9DE2E31-5BF0-4D98-984A-72C52FB5FB17","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6e39b6f3ca7446257ac0d46f8caa9a5a01cb5f64","datavalue":{"value":{"entity-type":"item","numeric-id":3738922,"id":"Q3738922"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1814249$E1500C10-9793-4248-8F6E-41B63789A1D3","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"06172695283fa433def6b778791e0a3953bdf8b2","datavalue":{"value":"https://doi.org/10.1007/bf01719934","type":"string"},"datatype":"url"},"type":"statement","id":"Q1814249$B986F0F7-8B20-4E28-B6FF-0BEADFEAD909","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"cd0a6e744b0e58fbe4f20096ff3a08c554a8b5ab","datavalue":{"value":"W2046012925","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1814249$2824F48F-752F-4BDF-916A-58ADCDE9F5C4","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"149de7420c61b089581cb1824380bc9d41ca8783","datavalue":{"value":{"entity-type":"item","numeric-id":3762096,"id":"Q3762096"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"849980379a96e156bd0862bfd9e3395f045daf8a","datavalue":{"value":{"amount":"+0.761890172958374","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":"Q1814249$A1E20F32-6C2F-4507-A12C-E42EF1AEC6EF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2727d11073d94bdfae4b3bb0a6732b8d1f222f04","datavalue":{"value":{"entity-type":"item","numeric-id":3818338,"id":"Q3818338"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"33e388adf3c1d62c95822345a177d4822df2fa38","datavalue":{"value":{"amount":"+0.7618462443351746","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":"Q1814249$17737A32-A8DB-4BFC-B2C1-C650A521DCC2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"56abdbc2c89b594f61d2458986d50d721cd5dedd","datavalue":{"value":{"entity-type":"item","numeric-id":3730365,"id":"Q3730365"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0e46983f0603e4c728e302badcfcff2c59b8dce7","datavalue":{"value":{"amount":"+0.7618453502655029","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":"Q1814249$463C9BB8-C606-4F08-BA38-DC43A0B37E4F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b37dce57c043de180ce644d15c5e243139c0fd4a","datavalue":{"value":{"entity-type":"item","numeric-id":908860,"id":"Q908860"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"358153a8da0f2c00acf724f64a3deda0f3d2257d","datavalue":{"value":{"amount":"+0.7379161715507507","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":"Q1814249$3D01B95C-934E-46BD-9A32-F4CBB529817E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1aa4fcfa236d0a7d908788168c9efb4966c9ce32","datavalue":{"value":{"entity-type":"item","numeric-id":3184586,"id":"Q3184586"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c0ac2b3ce66eda4f0abd0dd036c10418a965b2e1","datavalue":{"value":{"amount":"+0.7377645969390869","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":"Q1814249$6C1B9146-9A78-43E6-BB35-AF242F7F5B9A","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"A lower bound for the shortest Hamiltonean path in directed graphs","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/A_lower_bound_for_the_shortest_Hamiltonean_path_in_directed_graphs"}}}}}