The Nonnegative Node Weight j-Restricted k-Matching Problems

DOI10.1287/moor.2013.0624zbMath1309.90088OpenAlexW2011186779MaRDI QIDQ5244876

Yanjun Li

Publication date: 31 March 2015

Published in: Mathematics of Operations Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1287/moor.2013.0624

zbMATH Keywords

NP-completenesspolynomial-time algorithm\(k\)-matchingMIN-MAX theorem

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Combinatorial optimization (90C27)

Related Items

Packing $k$-Matchings and $k$-Critical Graphs ⋮ A note on \({\mathtt V}\)-free 2-matchings ⋮ An Edmonds-Gallai-type decomposition for the \(j\)-restricted \(k\)-matching problem

Cites Work

• Unnamed Item
• Unnamed Item
• Critical graphs, matchings and tours or a hierarchy of relaxations for the travelling salesman problem
• Maximum cardinality 1-restricted simple 2-matchings
• An extension of matching theory
• Packings by cliques and by finite families of graphs
• General factors of graphs
• On matroids induced by packing subgraphs
• Packing subgraphs in a graph
• Efficient subgraphs packing
• A necessary and sufficient condition for the existence of a path factor every component of which is a path of length at least two
• The Edmonds-Gallai decomposition for the \(k\)-piece packing problem
• Packing paths of length at least two
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• On the Complexity of General Graph Factor Problems
• Maximum Cardinality Simple 2-matchings in Subcubic Graphs
• Matroids Induced by Packing Subgraphs
• Paths, Trees, and Flowers
• The k‐piece packing problem
• A Short Proof of the Factor Theorem for Finite Graphs