Local maximum stable sets in bipartite graphs with uniquely restricted maximum matchings

DOI10.1016/S0166-218X(03)00398-6zbMath1028.05089OpenAlexW1990446008MaRDI QIDQ1414591

Vadim E. Levit, Eugen Mandrescu

Publication date: 4 December 2003

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0166-218x(03)00398-6

zbMATH Keywords

Bipartite graphMaximum matchingGreedoidLocal maximum stable setMaximum stable setUniquely restricted matching

Mathematics Subject Classification ID

Trees (05C05) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Structural characterization of families of graphs (05C75) Distance in graphs (05C12)

Related Items (16)

On unicyclic graphs with uniquely restricted maximum matchings ⋮ Critical sets, crowns and local maximum independent sets ⋮ Computing unique maximum matchings in \(O(m)\) time for König-Egerváry graphs and unicyclic graphs ⋮ On the hardness of deciding the equality of the induced and the uniquely restricted matching number ⋮ Local maximum stable set greedoids stemming from very well-covered graphs ⋮ On local maximum stable set greedoids ⋮ Triangle-free graphs with uniquely restricted maximum matchings and their corresponding greedoids ⋮ Crowns in bipartite graphs ⋮ Graph operations that are good for greedoids ⋮ On the equality of the induced matching number and the uniquely restricted matching number for subcubic graphs ⋮ VERY WELL-COVERED GRAPHS OF GIRTH AT LEAST FOUR AND LOCAL MAXIMUM STABLE SET GREEDOIDS ⋮ On Duality between Local Maximum Stable Sets of a Graph and Its Line-Graph ⋮ Approximating maximum uniquely restricted matchings in bipartite graphs ⋮ Zeros distribution of the reverse strong Turán expressions of polynomials sequences ⋮ The Clique Corona Operation and Greedoids ⋮ Unicycle graphs and uniquely restricted maximum matchings

Cites Work

• Greedoids
• The dependence graph for bases in matroids
• Alternating cycle-free matchings
• A new greedoid: The family of local maximum stable sets of a forest
• Introduction to Greedoids
• Vertex packings: Structural properties and algorithms
• Some Matching Problems for Bipartite Graphs
• Ranks of zero patterns and sign patterns^*
• Reducing the adjacency matrix of a tree
• On the jump number problem in hereditary classes of bipartite graphs
• Uniquely restricted matchings
• Unnamed Item

This page was built for publication: Local maximum stable sets in bipartite graphs with uniquely restricted maximum matchings