{"entities":{"Q1099088":{"pageid":1109840,"ns":120,"title":"Item:Q1099088","lastrevid":49143031,"modified":"2026-01-06T16:12:47Z","type":"item","id":"Q1099088","labels":{"en":{"language":"en","value":"Branch-and-bound and parallel computation: A historical note"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4039669"}},"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":"Q1099088$3A718670-E500-4CA4-9C2F-FD14F482CAFF","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"02e4398b43c192d1b72c4cae3e23982c6ba79fe1","datavalue":{"value":{"text":"Branch-and-bound and parallel computation: A historical note","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1099088$0A270198-3F30-41A9-B8AA-F37564C433C4","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"44242beb3ab7cc650a306847325e323efb0cf128","datavalue":{"value":"0637.90097","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1099088$64E01768-A55E-45F7-87C5-E013FE4BDD4E","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"6086768b82f546b31f53fb37f478bf384d806f5e","datavalue":{"value":"10.1016/0167-6377(88)90067-3","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1099088$F867734C-752D-4C47-969A-78E274EBFE6B","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"dc85af66dac78c71c47d6a3bca09878aa8e04967","datavalue":{"value":{"entity-type":"item","numeric-id":1099086,"id":"Q1099086"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1099088$ACD8F581-90C1-485B-A30E-401E408AF36E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"a1c26346d40b730bc09009d003fb3565eb0646e5","datavalue":{"value":{"entity-type":"item","numeric-id":163009,"id":"Q163009"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1099088$ED28E175-53BE-497A-85B9-A803685CFA15","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"331abd6d7629071fde0de66847ec2a87d692a08c","datavalue":{"value":{"entity-type":"item","numeric-id":1316094,"id":"Q1316094"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1099088$07CC971D-EEDB-480F-9DCD-E8F6C62D7810","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"f9747a37b0b56aeca2085282046e2737cd5087ca","datavalue":{"value":{"entity-type":"item","numeric-id":96289,"id":"Q96289"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1099088$6856E2FD-65CE-4A1A-9D75-8B9574B6B377","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"31a1937240ca4a323604b4728c31d242b5596d7c","datavalue":{"value":{"time":"+1988-00-00T00:00:00Z","timezone":0,"before":0,"after":0,"precision":9,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1099088$94BC9E2D-2075-4544-B15E-3F6BEDE455E1","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"67a90927e347422bdfd2c21470b5e411ad8c3fb8","datavalue":{"value":"This historical note summarizes what we believe to have been the first use of parallel processing to solve a combinatorial optimization problem by a branch-and-bound algorithm. In 1975, a branch-and-bound algorithm for the traveling salesman problem that used p parallel processors with shared memory was simulated on a single processor. The results show that the simultaneous exploration of several nodes of the search tree yields better feasible solutions earlier. This allows earlier pruning of branches and significantly reduces the number of nodes searched.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1099088$1D75ECAC-0EEA-4947-A9E3-FD188124BE9B","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"d2d4f4e28fa9ca38421c473fcb6ba728a44de59a","datavalue":{"value":"90C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1099088$85F7EC5F-A3D4-41EE-8344-AD66B077207E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"0b4fa5b59eb6fe6e43618f9e005f4a49f4390971","datavalue":{"value":"65K05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1099088$F5A78B9F-9987-4F05-912C-D1D938A96903","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"3feee98fb6a1a95642ba0c6a16390527874922bf","datavalue":{"value":"90C10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1099088$A0F2A8E6-1092-4022-BB94-8541AE774DE7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"35cb8465ca85ba26995d54be2905dc35556d665c","datavalue":{"value":"90C27","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1099088$61157DE1-9C59-4172-B589-311410A09C95","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"06fd711492a14ee37b9f8472a0f0880978ff5865","datavalue":{"value":"4039669","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1099088$99D02957-A755-4C34-AA98-57489253ABBD","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"db5e0888fa9957c443e210eb3c88f717e276ae13","datavalue":{"value":"parallel processing","type":"string"},"datatype":"string"},"type":"statement","id":"Q1099088$82A4FD43-EF89-4D19-A922-EA39F6EA9CBB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"32b70193b15cfa9820eaa83513ddb2267d9b694a","datavalue":{"value":"branch-and-bound","type":"string"},"datatype":"string"},"type":"statement","id":"Q1099088$7AB5FA3C-1E43-4462-A91C-756A48F6D193","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0245a4aeb76b9b1dc04bb886490fa5ef546c3af6","datavalue":{"value":"traveling salesman","type":"string"},"datatype":"string"},"type":"statement","id":"Q1099088$EF2F784D-B6E3-42EC-B9B4-DAA3095750BF","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":"Q1099088$483D046B-7023-4BBB-9612-8BEC4599E33D","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"b9dd3fd11139e4e4b9357a653feb09737dfd07f4","datavalue":{"value":"https://doi.org/10.1016/0167-6377(88)90067-3","type":"string"},"datatype":"url"},"type":"statement","id":"Q1099088$D53A9A5D-FB96-4087-A417-D49A4E82BF8D","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"3527cf6b58d15f6a6bb96d202971c8868b92d313","datavalue":{"value":"W2003540175","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1099088$CE17D2EF-CADE-411A-91BA-32ED5FA172D0","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"c78be35af062d87514e700fcae1bf481daa865c9","datavalue":{"value":{"entity-type":"item","numeric-id":1111941,"id":"Q1111941"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1099088$C120D43C-1133-4809-896D-93FB6494F198","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"11be915a4bc4892b9840bd618f18907ed3e352bc","datavalue":{"value":{"entity-type":"item","numeric-id":5684831,"id":"Q5684831"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1099088$EC779DF0-C928-4D9B-AF66-19259BBB6C27","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"af19f40a86b1a81b10c5d2b02c9dee04a257de7f","datavalue":{"value":{"entity-type":"item","numeric-id":1076605,"id":"Q1076605"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1099088$897340EF-BB68-4E57-B110-BEB4F08DD185","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7affab4819e30e50dae85b765c447a4532629a7f","datavalue":{"value":{"entity-type":"item","numeric-id":3221759,"id":"Q3221759"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1099088$71C13F37-03ED-49AA-AD6D-02DBB845DC98","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e63144fedd5d628196b9bec7e8e7981c3d1e3ab6","datavalue":{"value":{"entity-type":"item","numeric-id":1095034,"id":"Q1095034"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1099088$4FC81EA4-3201-4FA9-BEC4-8C381E7F1EE3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bf81e6d9c234339876089445bc7b93bc07a95490","datavalue":{"value":{"entity-type":"item","numeric-id":3713596,"id":"Q3713596"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1099088$403C1C30-9234-41EB-9013-2751AE6F64D3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2e7f1c3ce9d73902b7d6bd19c425e17c45bcfc10","datavalue":{"value":{"entity-type":"item","numeric-id":3686027,"id":"Q3686027"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1099088$E2888A2A-07A7-47A3-82CD-BD6FC1979DC9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ff28545fc96bd2ab6b6fa070dffb76c3c015c206","datavalue":{"value":{"entity-type":"item","numeric-id":1107978,"id":"Q1107978"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1099088$4A70D0A2-C556-4B7C-8387-712DAFFE8513","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9d1e8cd6eb2e0a5b1dbc86fe07f978d07189e52c","datavalue":{"value":{"entity-type":"item","numeric-id":5543949,"id":"Q5543949"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1099088$98882E51-5D4A-48A2-B0DC-CD61CDC1CEFA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5591fbd517068532880c03802d7c593b1a82fa39","datavalue":{"value":{"entity-type":"item","numeric-id":1099088,"id":"Q1099088"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1099088$73013242-7064-4CF8-9554-C4C70C901AE3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9ecb2f8db87b095bb3a0c58a549a6a7976f43870","datavalue":{"value":{"entity-type":"item","numeric-id":3309033,"id":"Q3309033"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1099088$FEAB0B41-CF8E-4B76-AAFE-2734E595F36B","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b55a737efa3f7febf7ec6e8402f3ec4d15600290","datavalue":{"value":{"entity-type":"item","numeric-id":4394587,"id":"Q4394587"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5dff4297d2187ad5d6a8936a653169f02a36d3c3","datavalue":{"value":{"amount":"+0.7803316712379456","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":"Q1099088$C5E81B06-662F-49F5-BAFE-5E8C9743DCC6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"cfabc00957300996523fe122bcb0f64f97c512a6","datavalue":{"value":{"entity-type":"item","numeric-id":1268289,"id":"Q1268289"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e5d89b8fc400fb37ce0c5c0bd840f5172a2780f4","datavalue":{"value":{"amount":"+0.7803316116333008","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":"Q1099088$8026A899-BC09-4B20-A8F6-081EF4DF852E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"401814a53a95c0f134a5c80d55ccce83351ef22a","datavalue":{"value":{"entity-type":"item","numeric-id":1208509,"id":"Q1208509"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"50af30e2a4bf22e180e8462fa698830eb3548d69","datavalue":{"value":{"amount":"+0.7594209313392639","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":"Q1099088$91ACCF66-B8DB-47EA-BBF7-B45E75C83E57","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7e18ccdff280847a271d102158d59c9e5896c3fe","datavalue":{"value":{"entity-type":"item","numeric-id":3713596,"id":"Q3713596"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3960386a632afef8ea09e789ad300597f90936d5","datavalue":{"value":{"amount":"+0.7516961693763733","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":"Q1099088$9D7AFF8D-30C2-44E0-9C5B-23000B082324","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"247834a02dda5e7deec2632fd8131a3ca3aed8eb","datavalue":{"value":{"entity-type":"item","numeric-id":4836301,"id":"Q4836301"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d9cf9324ab6bf52b9ae0e5ed72e944e352563773","datavalue":{"value":{"amount":"+0.7476243376731873","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":"Q1099088$871999F1-D5D9-4F75-8DB1-704A688ECEB9","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1099088","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1099088"}}}}}