{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,11]],"date-time":"2026-02-11T19:38:15Z","timestamp":1770838695776,"version":"3.50.1"},"reference-count":18,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2019,11,6]],"date-time":"2019-11-06T00:00:00Z","timestamp":1572998400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2019,11,6]],"date-time":"2019-11-06T00:00:00Z","timestamp":1572998400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100007601","name":"Horizon 2020","doi-asserted-by":"publisher","award":["739574"],"award-info":[{"award-number":["739574"]}],"id":[{"id":"10.13039\/501100007601","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Comb Optim"],"published-print":{"date-parts":[[2020,1]]},"abstract":"<jats:title>Abstract<\/jats:title>\n<jats:p>A confluent and terminating reduction system is introduced for graphs, which preserves the number of their perfect matchings. A union-find algorithm is presented to carry out reduction in almost linear time. The K\u00f6nig property is investigated in the context of reduction by introducing the K\u00f6nig deficiency of a graph <jats:italic>G<\/jats:italic> as the difference between the vertex covering number and the matching number of <jats:italic>G<\/jats:italic>. It is shown that the problem of finding the K\u00f6nig deficiency of a graph is NP-complete even if we know that the graph reduces to the empty graph. Finally, the K\u00f6nig deficiency of graphs <jats:italic>G<\/jats:italic> having a vertex <jats:italic>v<\/jats:italic> such that <jats:inline-formula><jats:alternatives><jats:tex-math>$$G-v$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mrow><mml:mi>G<\/mml:mi><mml:mo>-<\/mml:mo><mml:mi>v<\/mml:mi><\/mml:mrow><\/mml:math><\/jats:alternatives><\/jats:inline-formula> has a unique perfect matching is studied in connection with reduction.<\/jats:p>","DOI":"10.1007\/s10878-019-00466-2","type":"journal-article","created":{"date-parts":[[2019,11,6]],"date-time":"2019-11-06T22:15:50Z","timestamp":1573078550000},"page":"273-292","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["On the K\u00f6nig deficiency of zero-reducible graphs"],"prefix":"10.1007","volume":"39","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-0996-8769","authenticated-orcid":false,"given":"Mikl\u00f3s","family":"Bartha","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mikl\u00f3s","family":"Kr\u00e9sz","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2019,11,6]]},"reference":[{"key":"466_CR1","first-page":"281","volume":"30","author":"M Bartha","year":"2006","unstructured":"Bartha M, Kr\u00e9sz M (2006) Deterministic soliton graphs. Informatica 30:281\u2013288","journal-title":"Informatica"},{"key":"466_CR2","doi-asserted-by":"crossref","unstructured":"Bartha M, Kr\u00e9sz M (2009) A depth-first algorithm to reduce graphs in linear time. In: Proceedings of the 11th international symposium on symbolic and numeric algorithms for scientific computing, Timisoara, Romania. IEEE Computer Society, pp 273\u2013281","DOI":"10.1109\/SYNASC.2009.48"},{"key":"466_CR3","unstructured":"Bartha M, Kr\u00e9sz M (2010) Efficient unique perfect matching algorithms. In: Proceedings of the 8th joint conference on mathematics and computer science, Kom\u00e1rno, Slovakia"},{"key":"466_CR4","first-page":"245","volume-title":"Handbook of theoretical computer science, vol B: formal models and semantics","author":"N Dershowitz","year":"1990","unstructured":"Dershowitz N, Jouannaud J-P (1990) Rewrite systems. In: van Leeuwen J (ed) Handbook of theoretical computer science, vol B: formal models and semantics. Elsevier, Amsterdam, pp 245\u2013320"},{"key":"466_CR5","doi-asserted-by":"publisher","first-page":"449","DOI":"10.4153\/CJM-1965-045-4","volume":"17","author":"J Edmonds","year":"1965","unstructured":"Edmonds J (1965) Paths, trees and flowers. Can J Math 17:449\u2013467","journal-title":"Can J Math"},{"key":"466_CR6","doi-asserted-by":"publisher","first-page":"209","DOI":"10.1016\/0022-0000(85)90014-5","volume":"30","author":"HN Gabow","year":"1985","unstructured":"Gabow HN, Tarjan RE (1985) A linear-time algorithm for a special case of disjoint set union. J Comput Syst Sci 30:209\u2013221","journal-title":"J Comput Syst Sci"},{"key":"466_CR7","doi-asserted-by":"publisher","first-page":"159","DOI":"10.1006\/jagm.2001.1167","volume":"40","author":"HN Gabow","year":"2001","unstructured":"Gabow HN, Kaplan H, Tarjan RE (2001) Unique maximum matching algorithms. J Algorithms 40:159\u2013183","journal-title":"J Algorithms"},{"key":"466_CR8","first-page":"135","volume":"8","author":"T Gallai","year":"1963","unstructured":"Gallai T (1963) Neuer Beweis eines Tutte-schen Satzes. Magyar Tud Akad Mat Kutat\u00f3 Int K\u00f6zl 8:135\u2013139","journal-title":"Magyar Tud Akad Mat Kutat\u00f3 Int K\u00f6zl"},{"key":"466_CR9","first-page":"401","volume":"9","author":"T Gallai","year":"1964","unstructured":"Gallai T (1964) Maximale Systeme unabh\u00e4ngiger Kanten. Magyar Tud Akad Mat Kutat\u00f3 Int K\u00f6zl 9:401\u2013413","journal-title":"Magyar Tud Akad Mat Kutat\u00f3 Int K\u00f6zl"},{"key":"466_CR10","unstructured":"Korenwein V, Nichterlein A, Niedermeier R, Zschoche P (2018) Data reduction for maximum matching on real-world graphs: theory and experiments. In: Proceedings of the 26th annual European symposium on algorithms (ESA 2018), pp 53:1\u201353:13"},{"key":"466_CR11","first-page":"136","volume":"9","author":"A Kotzig","year":"1959","unstructured":"Kotzig A (1959) On the theory of finite graphs with a linear factor II. Mat-Fyz Casopis Slovensk Akad Vied 9:136\u2013159 (in Slovak)","journal-title":"Mat-Fyz Casopis Slovensk Akad Vied"},{"key":"466_CR12","doi-asserted-by":"crossref","first-page":"180","DOI":"10.37236\/667","volume":"18","author":"CE Larson","year":"2011","unstructured":"Larson CE, Pepper R (2011) Graphs with equal independence and annihilation numbers. Electron J Comb 18:180","journal-title":"Electron J Comb"},{"key":"466_CR13","unstructured":"Levit VE, Mandrescu E (2012) Independent sets in almost Konig\u2013Egervary graphs. In: Abstracts of the SIAM conference on discrete mathematics, Halifax, Canada, p 40, abstract MS21"},{"key":"466_CR14","doi-asserted-by":"publisher","first-page":"267","DOI":"10.1007\/s10878-015-9875-9","volume":"32","author":"VE Levit","year":"2016","unstructured":"Levit VE, Mandrescu E (2016) Computing unique maximum matchings in ${{\\cal{O}}} (m)$ time for K\u00f6nig\u2013Egerv\u00e1ry graphs and unicyclic graphs. J Comb Optim 32:267\u2013277","journal-title":"J Comb Optim"},{"key":"466_CR15","volume-title":"Matching theory","author":"L Lov\u00e1sz","year":"1986","unstructured":"Lov\u00e1sz L, Plummer MD (1986) Matching theory. North Holland, Amsterdam"},{"key":"466_CR16","volume-title":"Algorithms","author":"R Sedgewick","year":"2011","unstructured":"Sedgewick R, Wayne K (2011) Algorithms. Addison-Wesley, Boston"},{"key":"466_CR17","doi-asserted-by":"publisher","first-page":"215","DOI":"10.1145\/321879.321884","volume":"22","author":"RE Tarjan","year":"1975","unstructured":"Tarjan RE (1975) Efficiency of a good but not linear set union algorithm. J Assoc Comput Mach 22:215\u2013225","journal-title":"J Assoc Comput Mach"},{"key":"466_CR18","doi-asserted-by":"crossref","unstructured":"Thorup M (2000) Near-optimal fully-dynamic graph connectivity. In: Proceedings of the 32nd annual ACM symposium on the theory of computing ACM digital library, pp 343\u2013350","DOI":"10.1145\/335305.335345"}],"container-title":["Journal of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-019-00466-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10878-019-00466-2\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-019-00466-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,5]],"date-time":"2020-11-05T00:21:18Z","timestamp":1604535678000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10878-019-00466-2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,11,6]]},"references-count":18,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2020,1]]}},"alternative-id":["466"],"URL":"https:\/\/doi.org\/10.1007\/s10878-019-00466-2","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"value":"1382-6905","type":"print"},{"value":"1573-2886","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,11,6]]},"assertion":[{"value":"6 November 2019","order":1,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}