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

DOI10.1007/s10878-015-9875-9zbMath1354.90155arXiv1402.2903OpenAlexW2027498052MaRDI QIDQ328720

Publication date: 20 October 2016

Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1402.2903

zbMATH Keywords

core unicyclic graph Karp-Sipser leaf-removal algorithm König-Egerváry graph unique perfect matching

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35)

Related Items (3)

Combinatorial and spectral properties of König-Egerváry graphs ⋮ On some graphs with a unique perfect matching ⋮ On the König deficiency of zero-reducible graphs

Cites Work

Unnamed Item
Unnamed Item
Unnamed Item
Local maximum stable set greedoids stemming from very well-covered graphs
A characterization of the graphs in which the transversal number equals the matching number
The smallest values of algebraic connectivity for unicyclic graphs
The critical independence number and an independence decomposition
On the intersection of all critical sets of a unicyclic graph
On the spectral radius of unicyclic graphs with prescribed degree sequence
Minimizing the least eigenvalue of unicyclic graphs with fixed diameter
The spread of the unicyclic graphs
Ear-decompositions of matching-covered graphs
The uniquely solvable bipartite matching problem
The dependence graph for bases in matroids
Independence numbers of graphs - an extension of the Koenig-Egervary theorem
Combinatorial properties of the family of maximum stable sets of a graph
Local maximum stable sets in bipartite graphs with uniquely restricted maximum matchings
Very well covered graphs
On \(\alpha^{+}\)-stable König-Egerváry graphs
Critical independent sets and König-Egerváry graphs
On maximum matchings in König-Egerváry graphs
Triangle-free graphs with uniquely restricted maximum matchings and their corresponding greedoids
Unique Maximum Matching Algorithms
VERY WELL-COVERED GRAPHS OF GIRTH AT LEAST FOUR AND LOCAL MAXIMUM STABLE SET GREEDOIDS
Deciding the deterministic property for soliton graphs
Subgraph characterization of red/blue-split graph and kőnig egerváry graphs
Ranks of zero patterns and sign patterns^*
On the core of a unicyclic graph
Uniquely restricted matchings
On the structure of \(\alpha\)-stable graphs

This page was built for publication: Computing unique maximum matchings in \(O(m)\) time for König-Egerváry graphs and unicyclic graphs