{"entities":{"Q2056884":{"pageid":2067626,"ns":120,"title":"Item:Q2056884","lastrevid":78282953,"modified":"2026-05-06T11:13:32Z","type":"item","id":"Q2056884","labels":{"en":{"language":"en","value":"An incremental search heuristic for coloring vertices of a graph"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7440727"}},"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":"Q2056884$2D8A1443-4EFF-4AA9-AB15-2856B8318470","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"8effba433a4c5b8d4b5800bb1c1758b20e584d83","datavalue":{"value":{"text":"An incremental search heuristic for coloring vertices of a graph","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2056884$39866CEB-CD07-46C9-8454-15FE9E777714","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"5fc08c42b29551bc96016be196125eff62a113bc","datavalue":{"value":"1491.05077","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2056884$24852EAC-26C5-40B7-89AF-BDECFEFD1E8A","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"a6b4334ac32725594bd6ea3c3f4f2d5bb8785bfb","datavalue":{"value":"10.1007/978-3-030-63072-0_4","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2056884$A24A7B86-67FB-46F7-BF46-91EB69D58F25","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"23a0949f84aadd4c9fcaf6680067d189f44a02ea","datavalue":{"value":{"entity-type":"item","numeric-id":2056883,"id":"Q2056883"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2056884$D9DBFC54-C4F0-43D5-B0EA-B692F3B067D5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"5eaab4e5691184dc4dd06af228be42fb574a02bc","datavalue":{"value":{"entity-type":"item","numeric-id":324918,"id":"Q324918"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2056884$D50859AE-288B-45B9-91CD-74C6F0D8BA88","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"ccea0e72645421785937dbfd645828cb25e2fe7e","datavalue":{"value":{"time":"+2021-12-08T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2056884$1476B042-2B9C-4C04-A201-635D38E06013","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"3850c91fbb9633b1a9986e74a147cdec3df61ece","datavalue":{"value":"In this paper, the authors propose an incremental search heuristic (ISH) method for vertex coloring. First, they expound on the greedy coloring by predecessors and list several good orders of vertices for coloring. Then, the authors prove several related theorems about coloring order, by which an algorithm framework ISH is developed. The algorithm is simple and fast. On small sparse graphs, the algorithm can obtain the same or even a few smaller chromatic numbers than other classical algorithms. However, compared with the hybrid genetic algorithm, the accuracy of the algorithm needs to be improved. The algorithm only achieved a smaller chromatic number on one test set, while the genetic algorithm achieved a smaller chromatic number on six test sets.  For the entire collection see [Zbl 1465.05002].","type":"string"},"datatype":"string"},"type":"statement","id":"Q2056884$4280CA92-B00F-4C41-9EA9-A86A99825919","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2056884$4EA28E46-3245-484A-8E72-1B64B9A80269","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"cf979f4acdc6dac710cfd0a80dde6754b28a9043","datavalue":{"value":"05C42","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2056884$89AB0511-1BCD-4637-9156-025525A9A633","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"0134d0e82099c586fb46d456c955c04717853a02","datavalue":{"value":"7440727","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2056884$8C8B0AF7-87EA-4D18-9B52-0D3F3A35B1BB","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"85dfdbd7a975d6137b355769addaba184ea21dc4","datavalue":{"value":"vertex coloring","type":"string"},"datatype":"string"},"type":"statement","id":"Q2056884$4195A0F2-2068-46F7-8C51-035F7E97CFBC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2af51969b73542d6aab2bcded7015ec65969c29e","datavalue":{"value":"heuristic algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q2056884$975DEA86-A30B-4E26-8166-2CD214BEA0C5","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"1e1f410656486c4808aa81d9aba4daecf2ae80c6","datavalue":{"value":{"entity-type":"item","numeric-id":993697,"id":"Q993697"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2056884$6833DC83-FB60-4725-9412-C130921C0C8A","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":"Q2056884$07B86F97-E019-49E8-B342-5A21CA93A1B2","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"b791d2d7896365eb8fd4f3703a22e9063136d767","datavalue":{"value":"https://doi.org/10.1007/978-3-030-63072-0_4","type":"string"},"datatype":"url"},"type":"statement","id":"Q2056884$145ACD62-CBC0-461C-B337-8FEA1663B19E","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"8e000ca3f2c8bff05d0611e1c634599116fd5f81","datavalue":{"value":"W3135450210","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2056884$89DCDBC8-BBB6-48B4-90BD-8618363C4339","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"501aefe4754342fb8d5444baacca037714207964","datavalue":{"value":{"entity-type":"item","numeric-id":4999425,"id":"Q4999425"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2056884$E0C76D48-B162-4C08-8862-FC86EEDB96CF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7eb66b87688bc2ff814b7b9b7a7d0a2a04333d71","datavalue":{"value":{"entity-type":"item","numeric-id":2931428,"id":"Q2931428"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2056884$E960BD34-5532-4F06-AEE8-A2C411FB434F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"401b87a418815d8ebf2288d61413d916a2c72c30","datavalue":{"value":{"entity-type":"item","numeric-id":2489304,"id":"Q2489304"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2056884$1805F81B-EDB3-4DE9-B7C5-BB0B52AA22F1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7be3d31902a912348e24ead183b95d9b5a24c14c","datavalue":{"value":{"entity-type":"item","numeric-id":4247451,"id":"Q4247451"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2056884$D6F1099E-1F73-4500-BDF8-F64F12E455CA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a1d22e95cfb08114972c1514e26bef4d87d04d8a","datavalue":{"value":{"entity-type":"item","numeric-id":5524918,"id":"Q5524918"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2056884$29CF6987-983E-4D28-8BD1-14BD683BE7EE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4e7b26f6765114b169da5a79770389fa5bd84e12","datavalue":{"value":{"entity-type":"item","numeric-id":4175306,"id":"Q4175306"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2056884$0ECCD5F2-1DE2-46B2-827D-1D355FA71115","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":"Q2056884$E60EBA54-C65A-4F3D-8751-F10338010643","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1e9c86360d4b592a623a32491be38570987dd4b6","datavalue":{"value":{"entity-type":"item","numeric-id":3978838,"id":"Q3978838"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2056884$E59D0822-1E70-4A1A-86D9-8A18457875A0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fb5d30f6efb301b198edc644ad914957205518f4","datavalue":{"value":{"entity-type":"item","numeric-id":1043356,"id":"Q1043356"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2056884$1FDF7769-8E6B-4E96-901A-7646111F9FED","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bc427ad0a6bbd59e7a59ec760b852c817f659c2d","datavalue":{"value":{"entity-type":"item","numeric-id":4352217,"id":"Q4352217"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2056884$370A47CE-BC36-41F4-BE78-E41A384B5DF4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f099c8af7b6bae04f2637cc914f5615498541c4d","datavalue":{"value":{"entity-type":"item","numeric-id":580987,"id":"Q580987"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2056884$49F1D71C-79AD-45DF-83F0-475C966E08BF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fdd51985f8df50c8dac6708d27413a9259a40295","datavalue":{"value":{"entity-type":"item","numeric-id":5905438,"id":"Q5905438"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2056884$BC927982-8BC3-4320-B55A-B5D2DE016667","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"55b16b085550aa0b1ff43e0d0657a0dce948d880","datavalue":{"value":{"entity-type":"item","numeric-id":2467358,"id":"Q2467358"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2056884$5FEE7CBF-373F-4796-9206-5E5696206007","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"69d1679c433e18d7dc712776c0bddf50297cee38","datavalue":{"value":{"entity-type":"item","numeric-id":2467355,"id":"Q2467355"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2056884$63199F41-A05F-4B92-BECA-BDD15AB1C18F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7f59db515c43f4547f4a98d1e0724be14239051c","datavalue":{"value":{"entity-type":"item","numeric-id":5687261,"id":"Q5687261"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2056884$827AB955-2DE5-451A-8339-F4FE650FEDE2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d6ca000fcae894c265c75c5fda3c61696db0212d","datavalue":{"value":{"entity-type":"item","numeric-id":4367049,"id":"Q4367049"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2056884$5168DCFE-9AA2-4C5E-A5D1-128057666DA4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"02002a4f06171d9334d50f5db40d8d16a424f04f","datavalue":{"value":{"entity-type":"item","numeric-id":2294722,"id":"Q2294722"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2056884$D866412A-681D-4331-9C29-CD2D72DB31C6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5c821d2530e6484cb1a76133c7994dadca82a3ce","datavalue":{"value":{"entity-type":"item","numeric-id":2176284,"id":"Q2176284"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2056884$A8190863-3319-4A6E-9F0F-498B9BA8BD03","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ec63705f0486714a2398e15ecdce9f9e56ece33e","datavalue":{"value":{"entity-type":"item","numeric-id":2664279,"id":"Q2664279"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2056884$534FC8D2-3B98-4909-BAF6-240F3C91CFE1","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"02bb28440a1da829cc718a88deb05eb52f2ffc54","datavalue":{"value":{"entity-type":"item","numeric-id":3352500,"id":"Q3352500"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"fd85b360e3475b5f05220a3066b27f9b97a31012","datavalue":{"value":{"amount":"+0.788742184638977","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":"Q2056884$3942C5E8-2291-4D30-BEC4-2EC9872A807D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"28f12bcc3a3fbf06b4de1d7f0db305b1301864bb","datavalue":{"value":{"entity-type":"item","numeric-id":3035310,"id":"Q3035310"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"048d610fc6d3d356ae52636d564513546107d560","datavalue":{"value":{"amount":"+0.7841108441352844","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":"Q2056884$1C4C21A6-E460-414F-88E0-578FE3F22FA9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5ca303718ff868c880179a3cefe652f9f18fb7ec","datavalue":{"value":{"entity-type":"item","numeric-id":5752591,"id":"Q5752591"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4d625100de3667988195546b4c59c6a06719f0ad","datavalue":{"value":{"amount":"+0.780872106552124","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":"Q2056884$F8C3E20E-BA36-4C1E-B1D2-22CFCAC8EF4A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2805305266bfa4523351660e8996e95a0ec6fbf8","datavalue":{"value":{"entity-type":"item","numeric-id":281816,"id":"Q281816"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8b42ffe225019d116b3436830f352cba25de82e3","datavalue":{"value":{"amount":"+0.7772833704948425","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":"Q2056884$A470BC0A-1989-45D4-9F19-628E01CABE5D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2a53465f6afa186261cca558bc472480a4eeb327","datavalue":{"value":{"entity-type":"item","numeric-id":2458929,"id":"Q2458929"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"06bbe7224b43d29a00e88c488dd8eefd54262c90","datavalue":{"value":{"amount":"+0.7737305760383606","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":"Q2056884$E449F75F-481E-4EE6-9B45-2927ADF5572B","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"An incremental search heuristic for coloring vertices of a graph","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/An_incremental_search_heuristic_for_coloring_vertices_of_a_graph"}}}}}