{"entities":{"Q2566021":{"pageid":2576764,"ns":120,"title":"Item:Q2566021","lastrevid":72794958,"modified":"2026-04-14T07:53:13Z","type":"item","id":"Q2566021","labels":{"en":{"language":"en","value":"The approximability of the weighted Hamiltonian path completion problem on a tree"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 2207185"}},"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":"Q2566021$7F24719A-CB32-4F2B-80FE-58882423CD42","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"f65a9e4949325d58e7baa294b25f8a0cbd28b360","datavalue":{"value":{"text":"The approximability of the weighted Hamiltonian path completion problem on a tree","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2566021$9C886CC1-9068-4798-B7DC-E04021F5D752","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"c4292dcbf1dce2e73f479478c95c8422d14941a2","datavalue":{"value":"1077.68081","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2566021$C216B4CA-C290-4E8A-BA7D-21D39676860F","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"3f04515c7438a5200250b884c7760c8f28e8088c","datavalue":{"value":{"entity-type":"item","numeric-id":2566020,"id":"Q2566020"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2566021$817831CE-1B3C-4546-859E-44A82F6E542C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"cced9d2657b346242e6916a01e994e415103bcdf","datavalue":{"value":{"entity-type":"item","numeric-id":286979,"id":"Q286979"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2566021$52D2CDFB-BDE6-4956-A38F-7D3A56D40687","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"47287d42254c668443f35e7681b0c02cf3b2e14b","datavalue":{"value":{"entity-type":"item","numeric-id":702771,"id":"Q702771"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2566021$792FD2D4-8AE1-45FA-A101-B3A7BEC18A34","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"f3c424cd94a60f9664f9fb69cc6027e75cc7ff3f","datavalue":{"value":{"entity-type":"item","numeric-id":123643,"id":"Q123643"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2566021$8563E3AC-4BFE-4972-9D9A-050581AB642A","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"6ec9da92ba7b4e525d61f27d0c249399f1779b4c","datavalue":{"value":{"time":"+2005-09-22T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2566021$E6F9D8E0-4E7A-47C0-B1E3-0DCCD4E9EC94","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2566021$2CE300E0-64BC-4D89-834D-8890F6F84F34","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"d5da87a72c21717089feda882f568938059a9d84","datavalue":{"value":"05C05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2566021$F527043D-CE2C-42BA-8694-30A7AC65EB52","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"f3a5e47548ef139717b317f83801cfef606a623d","datavalue":{"value":"05C38","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2566021$0C61D786-DA2C-4F4C-A1D4-42C18F9F00A6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"749b7137f279a66a306e75e15f613231b281c1c5","datavalue":{"value":"05C85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2566021$6E25194C-C7C4-4280-9456-DD1229E56800","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a4228d21095b3348e9ea20aa0b63610107aad8cc","datavalue":{"value":"68W25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2566021$8F59BDB2-D4B0-4280-85BC-A8B67836B3FC","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"2efde5ed718a2bd30445327c157b66c8eab9cea5","datavalue":{"value":"2207185","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2566021$1EE4AFC3-C8A6-49CA-A500-FDE65F5C5CB1","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9f448c4c1497f69aa12db353f61dae0ece93405d","datavalue":{"value":"Hamiltonian path completion problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q2566021$403B338A-3550-4A4E-ABB9-04A5B572EE82","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d73370bca98b245fc04a970fd8098b8719db8ad2","datavalue":{"value":"Trees","type":"string"},"datatype":"string"},"type":"statement","id":"Q2566021$99747BE5-A17B-49FC-B3C6-A899C4E71862","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e63bfc0809b84f059e4b8b2681004808fad87715","datavalue":{"value":"Strongly NP-hard","type":"string"},"datatype":"string"},"type":"statement","id":"Q2566021$F4DB5699-618E-42B4-9DEA-C58A34E91EB7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"88af4e5a05d47825dc6aecd65a3f68a98232d37a","datavalue":{"value":"Approximation algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q2566021$E5D53482-3991-4D44-8508-A51430AB1208","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6bf7bc74afe0b3349a833abc62c15879247d7600","datavalue":{"value":"Fully polynomial-time approximation scheme","type":"string"},"datatype":"string"},"type":"statement","id":"Q2566021$B18C0D79-EB36-4F71-B7EE-C43D2F55F92B","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":"Q2566021$16816737-F7AC-4ED6-99AE-40039A466658","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"2ffa4ede51a515de2f5467fb69658e55bd8367fc","datavalue":{"value":"https://doi.org/10.1016/j.tcs.2005.03.043","type":"string"},"datatype":"url"},"type":"statement","id":"Q2566021$336BC30F-E3F6-40AB-9954-E7B7D5AAA547","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"227d24d4ce1bec4479c31800d7c2858710097b95","datavalue":{"value":"W2029561155","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2566021$C2439668-6B75-41C6-A6D7-9E46B212D438","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"b66d43343b5e258838f8347f60921b66aa51177c","datavalue":{"value":{"entity-type":"item","numeric-id":911770,"id":"Q911770"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2566021$3D252268-44A1-4748-A353-731A6CD9557C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5aa2a1ac4e864d41c30b8a828a68a91d18d8ecae","datavalue":{"value":{"entity-type":"item","numeric-id":4258216,"id":"Q4258216"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2566021$36AC0CB8-718E-44A8-A7F1-DC6D34B53654","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d5175a0c52543e9a486983cedbc3846a9743cc3a","datavalue":{"value":{"entity-type":"item","numeric-id":4299299,"id":"Q4299299"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2566021$AD6723E1-E920-4169-8D74-2F314CF7EDD5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b65a8a5581842586f798f1064b4750c719167264","datavalue":{"value":{"entity-type":"item","numeric-id":4310837,"id":"Q4310837"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2566021$B6855231-099F-446C-A4FB-23E0903B3792","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"85b8ca49a5619f41a7a3d54dbe6b8ab44e8b6c16","datavalue":{"value":{"entity-type":"item","numeric-id":4052166,"id":"Q4052166"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2566021$F4AD68A6-4030-451E-A44B-F7F9E417E646","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"dea894ecd998c141e7a6eb588e01242249c876aa","datavalue":{"value":{"entity-type":"item","numeric-id":1257337,"id":"Q1257337"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2566021$A2BF133B-19DC-4EB2-A1FE-ACD07C9A3878","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"71542908e9fad76674adf735afe61192d9d61ebe","datavalue":{"value":{"entity-type":"item","numeric-id":1336751,"id":"Q1336751"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2566021$BA1D3B49-BBEA-4E18-BCF2-424646324218","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"836ad2a04f82225da478ca9f694f5cd99360b315","datavalue":{"value":{"entity-type":"item","numeric-id":4198056,"id":"Q4198056"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2566021$EEE28D2C-1B45-4CDE-AF83-1B46668A150A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"18510c5b9d15ee46b96d01656bd46c91c194edde","datavalue":{"value":{"entity-type":"item","numeric-id":4050641,"id":"Q4050641"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2566021$57A40C4F-57B6-4C2F-9AD8-EF7D226408F2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f88cf5ca6dac86982c94be056f047a4ffd22123e","datavalue":{"value":{"entity-type":"item","numeric-id":4063184,"id":"Q4063184"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2566021$9DA03617-4397-4D42-AF2D-E6C6DD604279","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9b916828114586c907ab9703174b17d58bf1c2d1","datavalue":{"value":{"entity-type":"item","numeric-id":4114965,"id":"Q4114965"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2566021$2259910B-7BDE-4328-A104-C366E4376E30","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a9875cb22a8bf8c35efca2cae384031999b06525","datavalue":{"value":{"entity-type":"item","numeric-id":1226105,"id":"Q1226105"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2566021$86E8449B-51E9-4536-B936-7982FBAC0E4E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"08736496fad7f1ee1630e83b4f57fe1861c09098","datavalue":{"value":{"entity-type":"item","numeric-id":3048571,"id":"Q3048571"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2566021$2DAC4B52-D231-4FC4-87B8-F0F13738525E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"13c295423ec3d91cc1979ebb1d42d8adc698a8bf","datavalue":{"value":{"entity-type":"item","numeric-id":1903198,"id":"Q1903198"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2566021$364A3B42-4EB7-439F-AFF3-B5C93B370608","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"73e54b5dfb6dcd029fca22ec26c7b61c10787738","datavalue":{"value":{"entity-type":"item","numeric-id":1223159,"id":"Q1223159"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2566021$AD788434-78DE-4000-9AC9-C63B55ECB4A9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ce6133d293bb8bfa149948ffdc9b0f276ef45523","datavalue":{"value":{"entity-type":"item","numeric-id":1186548,"id":"Q1186548"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2566021$DFCDC502-818A-4544-B5E7-478F9DE30DD8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"48b538f59fa79437abf1147a3e501cd84d06d7c9","datavalue":{"value":{"entity-type":"item","numeric-id":4697080,"id":"Q4697080"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2566021$F51E9CB5-E5B0-41FE-9F0D-11C0716EF459","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bdf376f2946131481bf0c634e0ff1ff4924c8e63","datavalue":{"value":{"entity-type":"item","numeric-id":4119042,"id":"Q4119042"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2566021$973AFFB0-07AD-490D-90FC-E4DC2ED80D3E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9ae6531ddd34dd32c46772f585d82684b355ed87","datavalue":{"value":{"entity-type":"item","numeric-id":4097319,"id":"Q4097319"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2566021$542A1416-1703-4F05-A78F-C32D312F44E8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"73f1c25976e6efee5ba6d0807d7e21d52879dca2","datavalue":{"value":{"entity-type":"item","numeric-id":1261472,"id":"Q1261472"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2566021$DC572859-7414-4A7D-A3C1-D49C007E5081","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c26656ed385dde7973899e5ffff19b47113bb936","datavalue":{"value":{"entity-type":"item","numeric-id":1960660,"id":"Q1960660"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2566021$2975E9E2-A462-4B08-94AA-7C27B361E572","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"86856c91d67aa6fdb4edb9a390bc03a0e72b58d9","datavalue":{"value":{"entity-type":"item","numeric-id":1342260,"id":"Q1342260"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2566021$413C6D46-BE11-475C-9354-7990903B7A65","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"de983faf738b3bed6cb71e37c3ee6ddb4fba35b7","datavalue":{"value":"10.1016/J.TCS.2005.03.043","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2566021$547C5C04-5A55-4DE3-84F4-C60C4DBD72C5","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"87faf3f20e279e4eba5dd72fc54c6fdcc41705c4","datavalue":{"value":{"entity-type":"item","numeric-id":4472488,"id":"Q4472488"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b785b57d40069e9d5b1427603b2854f7a2d31e4c","datavalue":{"value":{"amount":"+0.9862089157104492","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":"Q2566021$5C1596B8-A00A-4C24-9B13-5E29CD189E9C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"935e23ebc5c2c1c474efa4ceff751d5d29f9522a","datavalue":{"value":{"entity-type":"item","numeric-id":4796447,"id":"Q4796447"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9d9e69e0b4b892977d1722f6cdb7ac1636ae8279","datavalue":{"value":{"amount":"+0.8021348714828491","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":"Q2566021$DEC1915E-6210-4168-891A-B830DB3A55D5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fed7964f5cb12b9bc99b4c2c59d0bba4a80945dc","datavalue":{"value":{"entity-type":"item","numeric-id":706963,"id":"Q706963"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f8877b18a5ea21318ff8a587f8c420478fc6f2aa","datavalue":{"value":{"amount":"+0.7739204168319702","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":"Q2566021$2AB10DF5-CD54-489C-A939-D68510982878","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"66499fdaae6ef83717bb12300d4d7be60f3eef22","datavalue":{"value":{"entity-type":"item","numeric-id":5711527,"id":"Q5711527"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"57559ddf7f0b2808b124c0bcc70874381705044a","datavalue":{"value":{"amount":"+0.7722132205963135","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":"Q2566021$426C3087-9E2A-440C-9DB1-48197A095659","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f2c617a24c82cb23f1830ab85ee150f05366eb13","datavalue":{"value":{"entity-type":"item","numeric-id":3415353,"id":"Q3415353"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"cba41c0005a28ef05148143e7677fdf5a74f356e","datavalue":{"value":{"amount":"+0.7717418074607849","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":"Q2566021$F924AD10-4E80-4171-B831-DFD98F3FA638","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"The approximability of the weighted Hamiltonian path completion problem on a tree","badges":[]}}}}}