Perfectly matchable subgraph problem on a bipartite graph

DOI10.1051/ro/2010004zbMath1218.05149OpenAlexW2138072774MaRDI QIDQ5189879

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/

zbMATH Keywords

bipartite graphperfect matchingextended polymatroidperfectly 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)

Related Items (1)

Perfect matching and polymatroids

Cites Work

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

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