Computing unique maximum matchings in $$O(m)$$ O ( m ) time for König–Egerváry graphs and unicyclic graphs

Vadim E. Levit () and Eugen Mandrescu ()
Additional contact information
Vadim E. Levit: Ariel University
Eugen Mandrescu: Holon Institute of Technology

Journal of Combinatorial Optimization, 2016, vol. 32, issue 1, No 17, 267-277

Abstract: Abstract Let $$\alpha \left( G\right) $$ α G denote the maximum size of an independent set of vertices and $$\mu \left( G\right) $$ μ G be the cardinality of a maximum matching in a graph $$G$$ G . A matching saturating all the vertices is a perfect matching. If $$\alpha \left( G\right) +\mu \left( G\right) =\left| V(G)\right| $$ α G + μ G = V ( G ) , then $$G$$ G is called a König–Egerváry graph. A graph is unicyclic if it is connected and has a unique cycle. It is known that a maximum matching can be found in $$O(m\cdot \sqrt{n})$$ O ( m · n ) time for a graph with $$n$$ n vertices and $$m$$ m edges. Bartha (Proceedings of the 8th joint conference on mathematics and computer science, Komárno, Slovakia, 2010) conjectured that a unique perfect matching, if it exists, can be found in $$O(m)$$ O ( m ) time. In this paper we validate this conjecture for König–Egerváry graphs and unicylic graphs. We propose a variation of Karp–Sipser leaf-removal algorithm (Karp and Sipser in Proceedings of the 22nd annual IEEE symposium on foundations of computer science, 364–375, 1981) , which ends with an empty graph if and only if the original graph is a König–Egerváry graph with a unique perfect matching (obtained as an output as well). We also show that a unicyclic non-bipartite graph $$G$$ G may have at most one perfect matching, and this is the case where $$G$$ G is a König–Egerváry graph.

Keywords: Unique perfect matching; Konig–Egervary graph; Unicyclic graph; Karp–Sipser leaf-removal algorithm; Core (search for similar items in EconPapers)
Date: 2016
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-015-9875-9 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:32:y:2016:i:1:d:10.1007_s10878-015-9875-9

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-015-9875-9

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().