{"entities":{"Q2664558":{"pageid":2675301,"ns":120,"title":"Item:Q2664558","lastrevid":57974424,"modified":"2026-04-03T07:31:37Z","type":"item","id":"Q2664558","labels":{"en":{"language":"en","value":"A fast distributed algorithm for \\((\\Delta+1)\\)-edge-coloring"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7428772"}},"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":"Q2664558$B3176D82-D12E-47CB-A67E-6BB6D5C83A73","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"d738b5eb287e36bdf407610b831041f28d92fa77","datavalue":{"value":{"text":"A fast distributed algorithm for \\((\\Delta+1)\\)-edge-coloring","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2664558$2BA0BDE4-684C-441E-BB18-9E4D8BC7EDBE","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"924461f55a5830da117b28e87fd1378f861b9e2b","datavalue":{"value":"1485.05048","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2664558$1B4906E9-B2C1-447D-9B3E-DF201ABC3F42","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"2492c774cc8e57e0398dc400af29bff5a70f0195","datavalue":{"value":{"entity-type":"item","numeric-id":294560,"id":"Q294560"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2664558$CFB39DC5-02C8-4012-9FE0-18C176D49672","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"f07f6fd6d97bd24ff86249abf8a501d3b63b437d","datavalue":{"value":{"entity-type":"item","numeric-id":256978,"id":"Q256978"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2664558$43A702CA-06B9-4C2B-A4D7-7C0E85B8EC80","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"9b583c20d2ff6d94455cad03e479bb4858d4835b","datavalue":{"value":{"time":"+2021-11-17T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2664558$5DBD32D3-1C5C-426E-8540-1E4118682696","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"8a11cb5835bb2f709943b051244b6d78c6478363","datavalue":{"value":"https://arxiv.org/abs/2006.15703","type":"string"},"datatype":"url"},"type":"statement","id":"Q2664558$C2B2704C-AEEC-42F8-A6DF-27F3199B9B41","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"12c97bde076d5b8ff7aed684eec8bf3582403efa","datavalue":{"value":"A local algorithm is a distributed algorithm that runs in constant time, which is independent of the size of the network concerned. In this paper, the author proposes a local algorithm to find a proper \\((\\Delta+1)\\)-edge-coloring of a graph of order \\(n\\) and maximum degree \\(\\Delta\\). In the beginning, he establishes the existence of such an algorithm that computes a \\((\\Delta+1)\\)-edge-coloring of a graph in \\(\\mathrm{poly}(\\Delta, \\log n)\\) rounds. In order to establish the same, the author uses the distributed approximation algorithm for hypergraph maximum matching and related arguments. Following this, he also explains that there is a connected augmenting subgraph \\(H\\) of the graph \\(G\\) under consideration such that \\(|E(H)| \\le O((\\log n)^2)\\).  In the following section, the notion of happy edges and the process of shifting have been introduced and explained with the help of suitable illustrations. The concepts of hopeful chains and successful chains follow and based on these, some interesting results are proved to establish the relations between these concepts. Later, the author describes a randomized algorithm, namely Multi-Step Vizing Algorithm, to build a happy chain starting with a specified uncolored edge of the graph and perform a probabilistic analysis of this algorithm.  The paper is well-written in insightful and logical manner. The style of presentation makes the reading a delightful experience. The author deserves much appreciation for the preparation of such a wonderful paper.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2664558$689E7B31-B55E-4C59-9A75-851ED3BFFA38","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2664558$759F398A-E500-4DA2-ABF1-9159F56D98D9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"749b7137f279a66a306e75e15f613231b281c1c5","datavalue":{"value":"05C85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2664558$FB1995D1-E9A5-4F03-87A7-739262E74C2A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"b65efe51b183d0f4a672427b8171cd1e14211cba","datavalue":{"value":"68W15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2664558$4C860ABC-CFB7-40A6-9683-E3C41F3FD898","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"c5a671b7d9d295dbb41a5d452a05ac7a44fca766","datavalue":{"value":"7428772","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2664558$C0490E64-64B8-4C7B-A1A9-98E6B7FBCC9C","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5460c444abb9d7604f90c4e16cd9cc2ad2a35457","datavalue":{"value":"edge-coloring","type":"string"},"datatype":"string"},"type":"statement","id":"Q2664558$B358EC73-7DFE-4D4D-9B8A-5A6DAD596874","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"387e204c6977d7b097ac93bf9a6ecf723e21df10","datavalue":{"value":"distributed algorithms","type":"string"},"datatype":"string"},"type":"statement","id":"Q2664558$87D3E65F-0021-4F35-ACC5-A9E7EFA5C9F1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4e5740860be10ad4dd34d19bcd51aafac8675af9","datavalue":{"value":"LOCAL model","type":"string"},"datatype":"string"},"type":"statement","id":"Q2664558$66F1A408-2179-4F58-BD92-18AEBDC65211","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"960868e761ff0337b9420c0b048d1daa1ff3d289","datavalue":{"value":"multi-step Vizing's algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q2664558$CB16CACE-09BF-4E4E-8BFC-B11B6568679B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"30f7111242bb9f8002a49a6d45f45f5479214dac","datavalue":{"value":"happy edges","type":"string"},"datatype":"string"},"type":"statement","id":"Q2664558$E7F7EB37-0ECC-4295-8EEA-09764C306281","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"41f523f37cb539bcdb4d52881589d9f3bcaac594","datavalue":{"value":"hopeful chains","type":"string"},"datatype":"string"},"type":"statement","id":"Q2664558$138A47D7-445B-4F7A-8C9A-487CC7B92078","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9279795db9f0901a3384d7332fb13d5c81a99d79","datavalue":{"value":"successful chains","type":"string"},"datatype":"string"},"type":"statement","id":"Q2664558$E201AE0B-EC81-4096-84E2-011B2065E309","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":"Q2664558$C00D2208-7D2C-4372-93A8-D25E6DDA450D","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"eb8c709c75f1986c236efcb72d9282c0fa126305","datavalue":{"value":"W3208522216","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2664558$8216ACAB-9FCD-4C3B-937D-9558C4CD9316","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"467979d98db9e05ef144a15cc4706cb28b6c2581","datavalue":{"value":{"entity-type":"item","numeric-id":3768419,"id":"Q3768419"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2664558$1A3A0CFD-6250-4367-A33E-FB83F593906B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a63c629fea996c5ff90f43945075a3fba115096b","datavalue":{"value":{"entity-type":"item","numeric-id":4980035,"id":"Q4980035"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2664558$58EBBC87-DA16-4D7E-AB8A-A3962C40BDD3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"aa4d7c7e3b9b8f0f827237d2d30f571feae08052","datavalue":{"value":{"entity-type":"item","numeric-id":4608064,"id":"Q4608064"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2664558$A7E37F85-B455-4201-A973-C88D70B8C510","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"650620a8abff65a78f27b6d9c816323baf828dab","datavalue":{"value":{"entity-type":"item","numeric-id":2829286,"id":"Q2829286"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2664558$FB41E75F-226B-4477-8405-06E4B3139BC3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7c32a9c7940b197d59ec6f1af6956af89a43e93b","datavalue":{"value":{"entity-type":"item","numeric-id":5230307,"id":"Q5230307"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2664558$5EE3A514-A7CA-449D-860C-264DAC7EB76F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6bc63e25f96016000176a9012e147a8d2d74a5cd","datavalue":{"value":{"entity-type":"item","numeric-id":3824434,"id":"Q3824434"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2664558$514DCA60-C71C-4ADB-A300-FBF701640E70","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ed3a3377688f1e4a281c4d108808de8755f7675c","datavalue":{"value":{"entity-type":"item","numeric-id":2006081,"id":"Q2006081"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2664558$E50A6818-BAFC-48BC-8AE9-0EC174288BE7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"308b35a6a5b4ac526a39371e07d1ce2848ff196f","datavalue":{"value":{"entity-type":"item","numeric-id":3990110,"id":"Q3990110"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2664558$6E792110-0F74-4974-A7F5-0D4FDA564D25","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8a5dd87f9b47ea169d77fccc0d3b1ab0e65eb8a1","datavalue":{"value":{"entity-type":"item","numeric-id":3756533,"id":"Q3756533"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2664558$BDAC7318-4974-4AD5-872D-50B4D272AF48","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2038d9318e291aaf9552a9eeca50679da0ed91aa","datavalue":{"value":{"entity-type":"item","numeric-id":5144922,"id":"Q5144922"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2664558$B8D5D246-6555-4210-9AA6-5130583358FA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d62f9ac8959a316d9d6224cee5e5b68d63b6eaa5","datavalue":{"value":{"entity-type":"item","numeric-id":3118960,"id":"Q3118960"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2664558$47221509-BEE6-4810-9A91-6322BF365C2D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6a9a7a665172f67197f2309f52d73eb22ee0442e","datavalue":{"value":{"entity-type":"item","numeric-id":5212777,"id":"Q5212777"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2664558$B207DF36-089E-4765-82DC-B78314EB977E","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"a1193b3e72da3fa88066f7597a446780caf100c7","datavalue":{"value":"10.1016/J.JCTB.2021.10.004","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2664558$7E9278C1-65B4-4F72-9A71-20605B961129","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f56f1b74a962a4d97da4427eb04b1d536746e782","datavalue":{"value":{"entity-type":"item","numeric-id":5212777,"id":"Q5212777"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1e1ece4317f5a40de9295ecbe456d77ffc0fdc21","datavalue":{"value":{"amount":"+0.9071247577667236","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":"Q2664558$C098AEAA-E4AA-46FE-86B6-C8E3A939DD1D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"50f3d69c215a9da9e4503c38a96bfeb886b401cd","datavalue":{"value":{"entity-type":"item","numeric-id":5230307,"id":"Q5230307"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"29827ebd6511144d124aa84203f40a438f93f477","datavalue":{"value":{"amount":"+0.8990400433540344","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":"Q2664558$AF97B9F5-013C-4E07-900D-91C1EA0C1487","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8399455ee074c2079b539992414782c0948999ae","datavalue":{"value":{"entity-type":"item","numeric-id":4796186,"id":"Q4796186"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"898bb6f380f2c707d087375ed8b8e0bfa013c2f5","datavalue":{"value":{"amount":"+0.8815594911575317","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":"Q2664558$7430CF59-5558-4E34-BC50-3AD1447D19CE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"77d72c67fc7fb00666d9efa24a63d8beeab984c3","datavalue":{"value":{"entity-type":"item","numeric-id":2768357,"id":"Q2768357"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"fea7490fd1ccd99c5b29c68c0ed5d02cde530429","datavalue":{"value":{"amount":"+0.8639059066772461","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":"Q2664558$4A2CCF93-7069-4E14-A9B5-A6B79B12DDFB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d1671c5c924070c4c9d53cf01db80e2135e9bf4b","datavalue":{"value":{"entity-type":"item","numeric-id":5363083,"id":"Q5363083"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0b77cc12d067d2333ee5fdea07639e5ca7b4a894","datavalue":{"value":{"amount":"+0.862270712852478","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":"Q2664558$46BB26AB-0B1A-41B2-87BA-F9871B06DA23","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2664558","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2664558"}}}}}