Uniquely restricted matchings

DOI10.1007/s00453-001-0004-zzbMath0980.68084OpenAlexW2044089009MaRDI QIDQ5946402

Moshe Lewenstein, Martin Charles Golumbic, Tirza Hirst

Publication date: 14 October 2001

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-001-0004-z

zbMATH Keywords

uniquely restricted matching

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10)

Related Items (34)

Disconnected matchings ⋮ 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 ⋮ From G-parking functions to B-parking functions ⋮ Security index based on perfectly undetectable attacks: graph-theoretic conditions ⋮ On the hardness of deciding the equality of the induced and the uniquely restricted matching number ⋮ Uniquely restricted matchings in subcubic graphs ⋮ Uniquely restricted matchings in subcubic graphs without short cycles ⋮ The Nonnegative Rank of a Matrix: Hard Problems, Easy Solutions ⋮ Weighted connected matchings ⋮ Degenerate matchings and edge colorings ⋮ Local maximum stable sets in bipartite graphs with uniquely restricted maximum matchings ⋮ Local maximum stable set greedoids stemming from very well-covered graphs ⋮ On local maximum stable set greedoids ⋮ Lower bounds on the uniquely restricted matching number ⋮ Zero forcing number, constrained matchings and strong structural controllability ⋮ Triangle-free graphs with uniquely restricted maximum matchings and their corresponding greedoids ⋮ Crowns in bipartite graphs ⋮ On complexity of special maximum matchings constructing ⋮ Strong structural input and state observability of linear time-invariant systems: graphical conditions and algorithms ⋮ Generalized subgraph-restricted matchings in graphs ⋮ On the equality of the induced matching number and the uniquely restricted matching number for subcubic graphs ⋮ On some hard and some tractable cases of the maximum acyclic matching problem ⋮ On some graphs with a unique perfect matching ⋮ On the complexity of minimum maximal uniquely restricted matching ⋮ VERY WELL-COVERED GRAPHS OF GIRTH AT LEAST FOUR AND LOCAL MAXIMUM STABLE SET GREEDOIDS ⋮ Parameterized Complexity of Discrete Morse Theory ⋮ Disconnected matchings ⋮ On Duality between Local Maximum Stable Sets of a Graph and Its Line-Graph ⋮ Approximating maximum uniquely restricted matchings in bipartite graphs ⋮ On the Maximum Uniquely Restricted Matching for Bipartite Graphs ⋮ Uniquely Restricted Matchings in Interval Graphs ⋮ Unicycle graphs and uniquely restricted maximum matchings

This page was built for publication: Uniquely restricted matchings