{"entities":{"Q1323480":{"pageid":1334230,"ns":120,"title":"Item:Q1323480","lastrevid":46322679,"modified":"2025-12-24T13:56:54Z","type":"item","id":"Q1323480","labels":{"en":{"language":"en","value":"A theory of alternating paths and blossoms for proving correctness of the \\(O(\\sqrt{V}E)\\) general graph maximum matching algorithm"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 567474"}},"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":"Q1323480$10C47C47-7C36-4BCA-BE42-AA5744523722","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"72c7e6a789de8ee80c9c3f71a74da1b008f18476","datavalue":{"value":{"text":"A theory of alternating paths and blossoms for proving correctness of the \\(O(\\sqrt{V}E)\\) general graph maximum matching algorithm","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1323480$A3193C5C-00DF-4150-8ADA-C79F6F02FC5B","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"6844067f29e11480eb44145e07f8f4b25a26efa2","datavalue":{"value":"0806.05058","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1323480$EB6978FB-E6BE-494B-9BD5-EF12E5EAFB1B","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"870a4f68776cae34ce52a0265f1367982a28ee36","datavalue":{"value":"10.1007/BF01305952","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1323480$28995D39-486A-492D-B967-749F5B06B893","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"d60cc394e2e4fe5c30e46e2359ff881fbae889f7","datavalue":{"value":{"entity-type":"item","numeric-id":593777,"id":"Q593777"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1323480$97C4CD15-0265-4CAA-B956-0186C3B6B6B6","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"a87e84d22579e69c48ca0a6d828473db4dde3dd6","datavalue":{"value":{"entity-type":"item","numeric-id":168579,"id":"Q168579"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1323480$17A6EB02-C502-4D49-A66C-A0558F8E1A06","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"39d0531cade64b487fc0bbaad6ff1ddcd7dd07ee","datavalue":{"value":{"time":"+1995-02-14T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1323480$27F2CEEB-9B87-4BC5-9C97-A58618F67855","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"ba7e072a5fe5f9876687c278e67daae16b0f3b5d","datavalue":{"value":"A matching algorithm is developed. Graph searching procedures are proposed; the synchronization of events plays a role very important in the conception. In Subsection 2.1 the bipartite case is studied, and the nonbipartite case is analyzed in 2.2. Two figures give the ideas related with the proposed linear time algorithm. Two theorems fix properties of the \\(\\text{minlevel}(v)\\) and \\(\\text{maxlevel}(v)\\) paths attainable. \\(\\text{Minlevel}(v)\\) is not breadth first search (BFS). The notion of  \\[ \\text{tenacity}(v)=\\text{evenlevel}(v)+ \\text{oddlevel}(v) \\]  is used as an alternative to BFS. Theorems 1 and 2 fix conditions under which \\(u\\) occurs at \\(\\text{minlevel}(u)\\) distance on another minlevel. The base of a vertex is defined in terms of tenacity. The main result is that the existence of a vertex of finite tenacity ensures the uniqueness of its base. The notion of base permits to introduce blossom as the set  \\[ \\bigl\\{v\\in V: \\text{tenacity}(v)\\leq t\\text{ and }\\text{base}_{>t}(v)= b\\bigr\\}. \\]  A theorem establishes that the shortest alternating paths from \\(\\text{base}(v)\\) to \\(v\\) are tied in a blossom. The nesting of blossoms and some relations between it and an even (odd) level are derived. A theorem establishes a connection among evenlevels, oddlevels of the end points of a bridge and tenacity. Two procedures are developed. The efficiency of one of them is characterized in terms of a set of edges. A theorem establishes the correctness of the algorithms.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1323480$EC1F2ED7-49CC-42F5-B601-B7EE5FF768EF","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"749b7137f279a66a306e75e15f613231b281c1c5","datavalue":{"value":"05C85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1323480$7BAF07AE-5C83-4BAF-BE7C-83B05D65FA1C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"625e55f1f2a96178239720bc1bbbe7ad21cf0a75","datavalue":{"value":"05C70","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1323480$47490A74-0A68-4E6D-BA25-FB876B0D62FC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"30d6d0de101c6ff200d712a6d7e331bcba20c783","datavalue":{"value":"90B40","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1323480$0A50C3F7-614C-462B-BB42-C385A447DA3F","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"68d45e6e5504b470e3be6aa0abce3d6708743ba0","datavalue":{"value":"567474","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1323480$93BE9FF3-8FE9-4087-AD40-8931668CDC2B","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d197cd588068c00e4c95496375d464dc9b33535e","datavalue":{"value":"matching algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q1323480$27B906E3-4B72-45BB-AE12-618086295E33","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6db4f7a6e74b0fb788c6c406afc713abfca9f275","datavalue":{"value":"searching procedures","type":"string"},"datatype":"string"},"type":"statement","id":"Q1323480$C1575939-DE98-4EFD-850D-AFFFA3C2B9F6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b4c27a8414208eba22b391b2c3a982e6e5e1d84b","datavalue":{"value":"linear time algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q1323480$FDDBA198-E5FE-4717-882F-D8AB271BB727","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ee3b5346efeee707b4934197b87a91f3ac88e0e7","datavalue":{"value":"tenacity","type":"string"},"datatype":"string"},"type":"statement","id":"Q1323480$805B5B59-61E2-4C05-B2DF-0A6C20ECE044","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"dc7028f677c081c63cf46f105c2a4dfd1d26ddbd","datavalue":{"value":"blossom","type":"string"},"datatype":"string"},"type":"statement","id":"Q1323480$B2F5909F-DC3F-4E59-9BC7-14EF1ED23DD2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"fd0c53925306220cae73425f7d3f63cfc98e9c10","datavalue":{"value":"alternating paths","type":"string"},"datatype":"string"},"type":"statement","id":"Q1323480$99B0886B-8DA6-4B7A-A5AE-E6198421102B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f9ac4ef6ef6c5f8856ee80195276e724e0b6225a","datavalue":{"value":"correctness","type":"string"},"datatype":"string"},"type":"statement","id":"Q1323480$E6B9D08B-BAEF-4436-B929-7786B1FB4DEA","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"e146cd479742131190191fb6e4c868c8b1c80b43","datavalue":{"value":{"entity-type":"item","numeric-id":591644,"id":"Q591644"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1323480$549B5010-6FF2-4850-9006-8B7E898943B4","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":"Q1323480$69B6312A-4132-4A43-9924-E234B45DDB10","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"f61c5d68d33f8ea7723f3ac70afbbc88052e3402","datavalue":{"value":{"entity-type":"item","numeric-id":3258697,"id":"Q3258697"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1323480$1553D31F-505A-4FA6-A867-F6CDB7B6E4E3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"184608d2b01c5a598fcf32bb7d4b28b414dbb79c","datavalue":{"value":{"entity-type":"item","numeric-id":4038720,"id":"Q4038720"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1323480$FAF94C52-204E-4DE8-BEBE-104C55B8349B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c39738cea79e11456d6583aec1786d79af209b23","datavalue":{"value":{"entity-type":"item","numeric-id":5341586,"id":"Q5341586"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1323480$AEF91E88-1963-47DA-A009-785A70714788","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2099f4cc0319bfd4935e61a7dd5931ecfc7bd7af","datavalue":{"value":{"entity-type":"item","numeric-id":4091992,"id":"Q4091992"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1323480$3560C54C-BEEC-42C4-A638-83BFAA922D06","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"17b46f23e1d95210ec444c78dd7a8edd18f2e48d","datavalue":{"value":{"entity-type":"item","numeric-id":1062461,"id":"Q1062461"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1323480$3BE80112-B482-4EBD-AC22-892C4CE2DCF4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"187e1fb158e6b4695b1eefc466a8e0535eaf95e7","datavalue":{"value":{"entity-type":"item","numeric-id":5682014,"id":"Q5682014"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1323480$E2192720-C173-4B8E-9069-BBE95E12C1E3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"004fcf36c9d84d518bd1c4d247f2882d8526b2f9","datavalue":{"value":{"entity-type":"item","numeric-id":1394096,"id":"Q1394096"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1323480$309A7E9D-F4A5-4C3D-A0FC-D486E726C240","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"dc6482fda869c7df0ed32fd6ade8f790a1ff04cc","datavalue":{"value":{"entity-type":"item","numeric-id":5585020,"id":"Q5585020"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1323480$AFA8CBE7-2400-4336-9F57-BCB5F00EAB56","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"08736496fad7f1ee1630e83b4f57fe1861c09098","datavalue":{"value":{"entity-type":"item","numeric-id":3048571,"id":"Q3048571"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1323480$E4BE5128-9895-4EE8-8F4C-16A830619EC8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"932383d1ac997ed208ef47dcb574b592efaf75b3","datavalue":{"value":{"entity-type":"item","numeric-id":4065031,"id":"Q4065031"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1323480$0AEEDB4A-0DDD-4372-8BF9-9CC39D3FCA5A","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"3892b1e3ab8bcbf316dc48c20ca7eeb09d9d180a","datavalue":{"value":"https://doi.org/10.1007/bf01305952","type":"string"},"datatype":"url"},"type":"statement","id":"Q1323480$E7FE97B8-EAEA-478F-A45C-86FB1D63E9D1","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"b3b847dafc2e64be440907c6785adbe9a87e1aeb","datavalue":{"value":"W1499313444","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1323480$8AC75C14-8F73-4252-BFE9-125683D4AD5C","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6f00a0fb38dcc405c45bc192cc887588ee6b2723","datavalue":{"value":{"entity-type":"item","numeric-id":4038720,"id":"Q4038720"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e402602c092369b094aeffc4aa38c7e2359070bd","datavalue":{"value":{"amount":"+0.854827880859375","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":"Q1323480$B6EA6670-40E3-4C70-8F34-E45408070CC1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"24a7587a167c1bbf33427df4ec70601493784769","datavalue":{"value":{"entity-type":"item","numeric-id":1105385,"id":"Q1105385"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"24f8bf9aceabd52c926285aac968ce8b1858fad2","datavalue":{"value":{"amount":"+0.8266375660896301","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":"Q1323480$1CEE487A-AFE7-457A-BE7F-61D73CDA6203","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"98f9e0e5a553edefd27a790b19f814727c69f381","datavalue":{"value":{"entity-type":"item","numeric-id":4302856,"id":"Q4302856"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2b27e50c17c6ecf30da70b9fdf9a7110fe7e6955","datavalue":{"value":{"amount":"+0.8217464089393616","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":"Q1323480$F8E35C78-9704-401F-B55A-0DCFA8CAFFBA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"bc013dc307ccd118403eb9ffeb7dd9c3d9326043","datavalue":{"value":{"entity-type":"item","numeric-id":4845365,"id":"Q4845365"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8dde74b085007fd0ffaa44b7b1b809b86afa9ce1","datavalue":{"value":{"amount":"+0.8204492926597595","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":"Q1323480$538E703C-41AE-42F8-ABB8-D47FCB9BDF6F","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1323480","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1323480"}}}}}