{"entities":{"Q4645944":{"pageid":6675525,"ns":120,"title":"Item:Q4645944","lastrevid":53317601,"modified":"2026-01-24T17:32:08Z","type":"item","id":"Q4645944","labels":{"en":{"language":"en","value":"The travelling salesman and the PQ-tree"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7000370"}},"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":"Q4645944$E74EA524-D843-478B-A89C-2F6D553FBFA3","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"440665fb7bb1864ce5f6527e3fa059afc8baaf9d","datavalue":{"value":{"text":"The travelling salesman and the PQ-tree","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q4645944$49C6E6FD-B4BC-4225-B0D6-9340715EFC80","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"9119a356102e8f44c6544275e27600b231225d04","datavalue":{"value":"1415.90060","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4645944$1604AAAB-EDC6-46B0-9779-3C904C3D72CA","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"d75b52c143b8989d2e37f0f56f702f92cae1af87","datavalue":{"value":"10.1007/3-540-61310-2_36","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4645944$810D2647-4602-4D01-99AB-8364A20F5F37","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"666364d845a4821db20440b841f1ca6c219a6664","datavalue":{"value":{"entity-type":"item","numeric-id":170644,"id":"Q170644"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4645944$E74E1551-7E84-47F6-9C2A-38DD92A51884","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"d610d74af67f3d7a1de35a584fe1a7834a0e2303","datavalue":{"value":{"entity-type":"item","numeric-id":207380,"id":"Q207380"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4645944$B2002857-781C-4242-B31F-A8108430CAD1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"4a99c5b7728e1965ef01019ed8fae6583a2f22e4","datavalue":{"value":{"entity-type":"item","numeric-id":170010,"id":"Q170010"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4645944$D8E010CE-4B04-4025-8C6E-7656B89AAEC2","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"536e91b90c2a3c71eef148769d69875689f7b0b9","datavalue":{"value":{"entity-type":"item","numeric-id":3186486,"id":"Q3186486"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4645944$D42A9CC5-313A-4DCE-92CB-2DB8D5DC3185","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"9c0a1786c627d23fd7437b6a14326c56be749770","datavalue":{"value":{"time":"+2019-01-11T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q4645944$3C92D4AF-50EA-4181-AB15-0B85241E851C","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"3feee98fb6a1a95642ba0c6a16390527874922bf","datavalue":{"value":"90C10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4645944$C56433D4-0CCC-48BA-AD9D-B5283C9FCAA8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"35cb8465ca85ba26995d54be2905dc35556d665c","datavalue":{"value":"90C27","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4645944$BB7B6976-B97A-434A-BB2D-8C8D61856010","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"8c719d1fe7888355e66bba7103ab16f056e0e3c8","datavalue":{"value":"7000370","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4645944$B8DF1299-92D3-4F5B-9576-F56F629CAFA9","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0a98fdc415b871902bf310caee2992f6f1b91c39","datavalue":{"value":"travelling salesman problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q4645944$D195FAFA-B300-455C-ABA4-690D5F629FDC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"fc544e482aa599702c82d69a25709014b297742d","datavalue":{"value":"polynomial algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q4645944$027ACA14-64D2-404B-8613-28A35BD56A66","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0d82cfa81638332a8c825bcbbd9d7f7f9c0c45be","datavalue":{"value":"dynamic programming","type":"string"},"datatype":"string"},"type":"statement","id":"Q4645944$67D5887C-D2E4-4D51-B1C6-0C19B0CC0E00","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c123c988a4455db85cc065f2e06e0a8051be65dd","datavalue":{"value":"combinatorial optimization","type":"string"},"datatype":"string"},"type":"statement","id":"Q4645944$04000792-6AED-4EE5-930B-D79EFCA1D67A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f4ff05e5bbecad5d9389a83ca10b7399b685717e","datavalue":{"value":"Euclidean travelling salesman problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q4645944$20211CAC-100D-4CFB-AE99-9C0D571C296B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2e59ac626b33db549bc8a94a3bacc0beb688ee58","datavalue":{"value":"PQ-tree","type":"string"},"datatype":"string"},"type":"statement","id":"Q4645944$98E2AB5D-95DD-410D-8ECD-3D6C34F3624B","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":"Q4645944$ADA04A03-152F-4B75-94CF-9517B6764F34","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"aaccc58e8dfb35186f0a3ba87648e8c4dc964b55","datavalue":{"value":"https://doi.org/10.1007/3-540-61310-2_36","type":"string"},"datatype":"url"},"type":"statement","id":"Q4645944$23E5C1BB-9B2D-44A8-8A3B-5319F3895FDB","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"68985588671df688d249503d6d92e335b824ebe9","datavalue":{"value":"W1678991643","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4645944$9D406876-1589-432B-9697-A064944DAB3A","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"528868b1eca69fffc21e426a5a0699a854b34b33","datavalue":{"value":{"entity-type":"item","numeric-id":1104753,"id":"Q1104753"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4645944$354864D9-CE17-4838-8521-2F0DF625E36E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9914f8121a32baf6895c6797ec99c63c32102968","datavalue":{"value":{"entity-type":"item","numeric-id":1242450,"id":"Q1242450"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4645944$F6946EC0-2C48-4CD6-A486-8CD557EB0CF6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8d8d17332a9332ddce98bc929b0510b69761d7f3","datavalue":{"value":{"entity-type":"item","numeric-id":3360022,"id":"Q3360022"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4645944$EC0E7EB5-4222-44E2-89D1-C6E6FE5A5CF6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"666261474c9625949f651c962cde2d1f630ea4ba","datavalue":{"value":{"entity-type":"item","numeric-id":5202515,"id":"Q5202515"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4645944$678A3A09-BDAA-4B30-A758-B487297E6DD4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d518d0b844959e6a69fd5f3c3ce1068d3e9c7281","datavalue":{"value":{"entity-type":"item","numeric-id":2120141,"id":"Q2120141"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4645944$AEA6E39F-3D8E-466D-8425-EC873F04208F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7b2e34f2d00f3ab616b227145acdba74c6bec5ae","datavalue":{"value":{"entity-type":"item","numeric-id":5378825,"id":"Q5378825"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4645944$7567AD4B-3397-4BA4-BD0A-A9B48B82399D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1d2c893b7b17db5da0cf71bed489830282949b84","datavalue":{"value":{"entity-type":"item","numeric-id":3768703,"id":"Q3768703"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4645944$D3696EA0-837B-44EA-95F4-8DBA716A3EED","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"305990cab47347d26b508880daf4599932710fd4","datavalue":{"value":{"entity-type":"item","numeric-id":4347415,"id":"Q4347415"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4645944$52CF489D-68E5-4C5E-AF77-8B6A4ADD04AC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7cbad4944f17afff471966f84ddba81383864ae6","datavalue":{"value":{"entity-type":"item","numeric-id":3292045,"id":"Q3292045"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4645944$4F309219-3331-4DFC-8699-E4A8041F45F3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a96c989d90e2e2902db5020c0cdff50569413a7e","datavalue":{"value":{"entity-type":"item","numeric-id":3693290,"id":"Q3693290"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4645944$59D3926C-466A-42FA-8B35-2FD13F2B67C1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d2d7941d0b26099a80a70765368bbd5212826ec8","datavalue":{"value":{"entity-type":"item","numeric-id":3677509,"id":"Q3677509"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4645944$1CE26149-AFB6-439F-98A9-6FE529E5F9BD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2c85ad1c11b4c2c66512da23bc9ecc32c36b4a62","datavalue":{"value":{"entity-type":"item","numeric-id":5510390,"id":"Q5510390"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4645944$6D03343A-6A69-48E6-9930-ADEED6EA3C8F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c8b5333eb1b8ed8e5a5b9dc077a98e596db9c9cc","datavalue":{"value":{"entity-type":"item","numeric-id":1250163,"id":"Q1250163"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4645944$08068820-0F16-40E6-9DBD-A7485F261B46","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9ad86ed10f9dbc91aef6fdb78e5f6edf0ab2f5e6","datavalue":{"value":{"entity-type":"item","numeric-id":4739657,"id":"Q4739657"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4645944$77E5EFF7-EA8D-4969-8CAB-BDDC91A46200","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4b56ed418b4cf68bf008580e23ec8cb70de24f2d","datavalue":{"value":{"entity-type":"item","numeric-id":3343801,"id":"Q3343801"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4645944$E7B5A5CD-12ED-4416-AD96-7EFCC841A023","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7bf0c7130bec9c610b5a153ea94c2017bd9460e3","datavalue":{"value":{"entity-type":"item","numeric-id":3931037,"id":"Q3931037"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4645944$BD0A3E30-DA25-4213-986A-B572F4EC86E4","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6c76ea9840d4939d45ba685d17fd34306fe3cd24","datavalue":{"value":{"entity-type":"item","numeric-id":2757553,"id":"Q2757553"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"97888d4b192eb4ec0db93a71b697bc2b178a42be","datavalue":{"value":{"amount":"+0.9170407056808472","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":"Q4645944$98C46881-6104-45B5-9C41-78D8DB88443C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e0723bd9d481f99f3a89b8bc03a7157fc1de133d","datavalue":{"value":{"entity-type":"item","numeric-id":1805008,"id":"Q1805008"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7299f7201ba63faa0db3078aa64974709e8bd217","datavalue":{"value":{"amount":"+0.8185732960700989","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":"Q4645944$F19386DB-A80D-459B-8AE5-B55F290803A2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"840244e18f8c54fe34fa268d5f49970b35c9174d","datavalue":{"value":{"entity-type":"item","numeric-id":5406222,"id":"Q5406222"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"fdc8c91d55a0d75d21b4db7b1f6324f834f9fd16","datavalue":{"value":{"amount":"+0.8111445307731628","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":"Q4645944$6B9B08C6-0032-4B59-BA80-733312E28B0D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1e96be937adf3eeaa924e7fc5a9121872d6150d2","datavalue":{"value":{"entity-type":"item","numeric-id":3104252,"id":"Q3104252"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b02ad8bfeaa8ac5df6f4482cdc58a5e38834ad75","datavalue":{"value":{"amount":"+0.8055795431137085","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":"Q4645944$FFEC11E7-6ED7-4535-9E2F-A9E24B1A67B8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2bb4e255666e6ea6efbe1bb0b381f192b731e269","datavalue":{"value":{"entity-type":"item","numeric-id":1575073,"id":"Q1575073"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"183f4a6d794fb04f42ad89aeb5c9357d8fae3117","datavalue":{"value":{"amount":"+0.7956323027610779","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":"Q4645944$31E96496-0599-4499-B743-777F660E0B2C","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:4645944","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:4645944"}}}}}