Perfectly matchable subgraph problem on a bipartite graph

DOI10.1051/RO/2010004MaRDI QIDQ5189879zbMATH OpenOpenAlexFDO

Authors Firdovsi Sharifov

Publication date 11 March 2010

Published in RAIRO - Operations Research (Search for Journal in Brave)

Full work available at URL http://www.numdam.org/item?id=RO_2010__44_1_27_0/, https://eudml.org/doc/44705

zbMATH Keywords

bipartite graphextended polymatroidperfect matchingperfectly matchable subgraph

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85)

Recommendations

• Perfect matchings and extended polymatroid
• Perfect matching and polymatroids
• On separation and adjacency problems for perfectly matchable subgraph polytopes of a graph
• The perfectly matchable subgraph polytope of an arbitrary graph
• Optimum matchings in weighted bipartite graphs

Cites work

• A separation algorithm for the matchable set polytope
• Computing a maximum cardinality matching in a bipartite graph in time \(O(n^{1,5}\sqrt{m/\log \,n})\)
• Minimum cut problem using bases of extended polymatroids
• Network flows. Theory, algorithms, and applications.
• Signature Methods for the Assignment Problem
• The Maximum Induced Bipartite Subgraph Problem with Edge Weights
• The perfectly matchable subgraph polytope of a bipartite graph
• The perfectly matchable subgraph polytope of an arbitrary graph

Cited in

(9)

• Reconfiguration of maximum weight \(b\)-matchings in a graph
• Reconfiguration of maximum-weight b-matchings in a graph
• The Maximum Induced Bipartite Subgraph Problem with Edge Weights
• On the NP-completeness of the perfect matching free subgraph problem
• A weighted perfect matching with constraints on weights of its parts
• Perfect matching and polymatroids
• The perfectly matchable subgraph polytope of an arbitrary graph
• On separation and adjacency problems for perfectly matchable subgraph polytopes of a graph
• Perfect matchings and extended polymatroid

This page was built for publication: Perfectly matchable subgraph problem on a bipartite graph

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5189879)