{"entities":{"Q580987":{"pageid":582754,"ns":120,"title":"Item:Q580987","lastrevid":62924847,"modified":"2026-04-11T09:01:11Z","type":"item","id":"Q580987","labels":{"en":{"language":"en","value":"Using tabu search techniques for graph coloring"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4018399"}},"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":"Q580987$9F831EB2-61B5-456C-9DDD-E9CDA444214A","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"45eda70843cdfc1da05379146932b4826cbc5c50","datavalue":{"value":{"text":"Using tabu search techniques for graph coloring","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q580987$45A45133-8629-48FF-AE97-CA3EDA1DB85F","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"5467d07f18d82c7633598448a9469b4340c28ec4","datavalue":{"value":"0626.68051","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q580987$13F9A320-CE75-45F2-B297-C6A469D8982D","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"737c5957514c21bf850aa372ce758faeaf76bfc4","datavalue":{"value":"10.1007/BF02239976","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q580987$20085630-9122-4B6B-8F70-81EA1FA1C95E","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"467bce3dcf8136ea7a4832a7c85d350a56e9a245","datavalue":{"value":{"entity-type":"item","numeric-id":224825,"id":"Q224825"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q580987$F6C8BA41-04B1-4B6F-B93E-1533A76B9C64","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"4249c9a7a0b14df0599e70315ca2a040457d857c","datavalue":{"value":{"entity-type":"item","numeric-id":260023,"id":"Q260023"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q580987$F7A43B24-3DFB-4C57-9D69-4B021E351167","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"b79ece58f33b59758a066cb6b9ee149bab3a2c9a","datavalue":{"value":{"entity-type":"item","numeric-id":167642,"id":"Q167642"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q580987$695B2883-5132-44B4-A230-8CFF9AE94D3D","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"5ae48c61eed19d1e1e1f33f9255d5b329362d064","datavalue":{"value":{"time":"+1987-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":"Q580987$BB4AF3FA-D0BE-4ABB-931F-7F75B8810296","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"19b5eb9f8ccffda565b20e21a74b780e7e312847","datavalue":{"value":"Tabu search techniques are used for moving step by step towards the minimum value of a function. A tabu list of forbidden movements is updated during the iterations to avoid cycling and being trapped in local minima. Such techniques are adapted to graph coloring problems. We show that they provide almost optimal colorings of graphs having up to 1000 nodes and their efficiency is shown to be significantly superior to the famous simulated annealing.","type":"string"},"datatype":"string"},"type":"statement","id":"Q580987$2C8FC3B6-A705-470B-9640-602311E0D588","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q580987$DC70E592-0262-4699-9AED-AC06B8F2968E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"2f9920e258389d79a7ef76ef96a77d2e9cc60267","datavalue":{"value":"05-04","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q580987$912CCD5E-7535-46BD-B7B3-6D525F1E5525","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q580987$7D63476D-E098-4F87-9CBA-4FFFD486ED62","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"b14281134286f276e8cd72c188b1abd697706b08","datavalue":{"value":"4018399","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q580987$7C9E36D4-6736-484D-8508-729D2DFE3F6A","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e09726da53e95ae004a19637083ed8dc4eff896f","datavalue":{"value":"graph coloring","type":"string"},"datatype":"string"},"type":"statement","id":"Q580987$51E86F63-8381-458C-B7D6-687AFA81A3EC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c8e00475554cb95f00d16db197d5817dede1318d","datavalue":{"value":"tabu search","type":"string"},"datatype":"string"},"type":"statement","id":"Q580987$5AD66DF1-0B83-4788-9EFB-62E44FE37A53","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"605eaf52a7d40b4ca440dd997a658542e33d5665","datavalue":{"value":"simulated annealing","type":"string"},"datatype":"string"},"type":"statement","id":"Q580987$ABE77272-19A1-45CF-9C7C-F58DC57F483F","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":"Q580987$090CE988-7007-4D39-B1B0-F02B5B64A193","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"a0388cf2ff1e7bf2b4fbc0f8cf2b7868f7fb86b6","datavalue":{"value":{"entity-type":"item","numeric-id":3715148,"id":"Q3715148"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q580987$FAFCA234-F8E2-4855-8AE5-195E3FBC7D20","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8205d99991e663bd0841aadc5bee21beef2c309a","datavalue":{"value":{"entity-type":"item","numeric-id":581241,"id":"Q581241"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q580987$8E535D6B-63BD-43E2-ADDD-DBB6D39647C0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"aa03fdd53c1b9f8eb1141c56fc2bb4afc212b013","datavalue":{"value":{"entity-type":"item","numeric-id":1821034,"id":"Q1821034"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q580987$1FB2360F-1F88-4814-9BA4-F714C84D8395","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"82d072e0713e5042bd242eed26b899a084f816f9","datavalue":{"value":"https://doi.org/10.1007/bf02239976","type":"string"},"datatype":"url"},"type":"statement","id":"Q580987$7FA03F79-C026-4653-A4E9-38EB09D960E9","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"3953110047b59fd783414dfa8e6b117e763bfadc","datavalue":{"value":"W2168000780","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q580987$4A717DF4-AEB5-4A76-AC0F-C1D2A7335CF0","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e850e585e1d8a6c1eecac14d7a3aa7837b606e28","datavalue":{"value":{"entity-type":"item","numeric-id":4298852,"id":"Q4298852"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"79cdcb362c797cfbfcbe1d9e7837328ff5133f14","datavalue":{"value":{"amount":"+0.8555044531822205","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":"Q580987$A78034BE-DE6C-4277-AA44-CB1C2A290F87","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5a02eb4216de196e7d20cf0751ad9a5ae136f8c8","datavalue":{"value":{"entity-type":"item","numeric-id":2489304,"id":"Q2489304"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"93a9aea798cbbe276120e8c9ae7742d291ca32c7","datavalue":{"value":{"amount":"+0.851401686668396","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":"Q580987$8BFE487B-04F9-47B9-9A56-6B01DB44A817","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1f6dd6f0afb4dd823fd894bdfe71f1fb8aa72c30","datavalue":{"value":{"entity-type":"item","numeric-id":4495173,"id":"Q4495173"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2191a09322cf17555e40b8abc6709c65486392f3","datavalue":{"value":{"amount":"+0.833443284034729","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":"Q580987$20AA42CE-DD8D-4F95-B4FB-2FAFC8AC841A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"00c52ad40253c4012f80afb2f3c95fb006379c99","datavalue":{"value":{"entity-type":"item","numeric-id":1861926,"id":"Q1861926"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"fb16f0ed4d4ed7091c249178aeaf90e4cae712f3","datavalue":{"value":{"amount":"+0.8318021893501282","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":"Q580987$3B4210B9-1020-4145-B73C-042F7045F90D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"33a4a80b5e5f74d236ce7f48b1e51dde9b6e25e4","datavalue":{"value":{"entity-type":"item","numeric-id":1802494,"id":"Q1802494"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"868ed6a05197f53f73c0d5f729d668e7c81832a7","datavalue":{"value":{"amount":"+0.8219087719917297","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":"Q580987$7FCE93FC-2742-4974-A9A9-E3C184ABEC6C","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Using tabu search techniques for graph coloring","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Using_tabu_search_techniques_for_graph_coloring"}}}}}