On Maximum Cost $K_{t,t}$‐Free t‐Matchings of Bipartite Graphs

DOI10.1137/060652282zbMath1139.05310OpenAlexW2073506427MaRDI QIDQ3503219

Márton Makai

Publication date: 22 May 2008

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/060652282

zbMATH Keywords

submodularityinteger polyhedrarestricted matchings

Mathematics Subject Classification ID

Integer programming (90C10) Minimax problems in mathematical programming (90C47) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Optimality conditions and duality in mathematical programming (90C46) Hypergraphs (05C65) Combinatorial optimization (90C27) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Vertex degrees (05C07)

Related Items (13)

Weighted Triangle-Free 2-Matching Problem with Edge-Disjoint Forbidden Triangles ⋮ Excluded $t$-Factors in Bipartite Graphs: Unified Framework for Nonbipartite Matchings, Restricted 2-Matchings, and Matroids ⋮ Decomposition theorems for square-free 2-matchings in bipartite graphs ⋮ A Weighted K t,t -Free t-Factor Algorithm for Bipartite Graphs ⋮ An algorithm for \((n-3)\)-connectivity augmentation problem: jump system approach ⋮ A simple algorithm for finding a maximum triangle-free \(2\)-matching in subcubic graphs ⋮ A proof of Cunningham's conjecture on restricted subgraphs and jump systems ⋮ An algorithm for finding a maximum \(t\)-matching excluding complete partite subgraphs ⋮ Matchings under distance constraints. I ⋮ Finding a maximum 2-matching excluding prescribed cycles in bipartite graphs ⋮ A simple combinatorial algorithm for restricted 2-matchings in subcubic graphs -- via half-edges ⋮ Decomposition Theorems for Square-free 2-matchings in Bipartite Graphs ⋮ Weighted triangle-free 2-matching problem with edge-disjoint forbidden triangles

This page was built for publication: On Maximum Cost $K_{t,t}$‐Free t‐Matchings of Bipartite Graphs