Weighted triangle-free 2-matching problem with edge-disjoint forbidden triangles

DOI10.1007/S10107-021-01661-YMaRDI QIDQ2118149zbMATH OpenOpenAlexFDO

Authors Yusuke Kobayashi

Publication date 22 March 2022

Published in Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL http://hdl.handle.net/2433/252767

zbMATH Keywords

extended formulationpolynomial-time algorithmrestricted 2-matchingtriangle-free

Mathematics Subject Classification ID

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

Recommendations

• Weighted triangle-free 2-matching problem with edge-disjoint forbidden triangles
• A fast scaling algorithm for the weighted triangle-free 2-matching problem
• A fast scaling algorithm for the weighted triangle-free 2-matching problem
• Constrained weighted matchings and edge coverings in graphs
• scientific article; zbMATH DE number 4062620
• Triangle-free 2-matchings revisited
• Triangle-free 2-matchings revisited
• Maximum weight edge-constrained matchings
• Approximating minimum weight perfect matchings for complete graphs satisfying the triangle inequality
• Weighted domination in triangle-free graphs

Cites work

• A matching problem with side conditions
• A proof of Cunningham's conjecture on restricted subgraphs and jump systems
• A simple algorithm for finding a maximum triangle-free 2-matching in subcubic graphs
• A weighted \(K_{t,t}\)-free \(t\)-factor algorithm for bipartite graphs
• A weighted linear matroid parity algorithm
• An algorithm for \((n-3)\)-connectivity augmentation problem: jump system approach
• Combinatorial algorithms for matchings, even factors and square-free 2-factors
• Decomposition theorems for square-free 2-matchings in bipartite graphs
• Excluded \(t\)-factors in bipartite graphs: a unified framework for nonbipartite matchings and restricted 2-matchings
• Extended formulations in combinatorial optimization
• Finding a maximum 2-matching excluding prescribed cycles in bipartite graphs
• Finding maximum square-free 2-matchings in bipartite graphs
• Geometric algorithms and combinatorial optimization
• scientific article; zbMATH DE number 1342133 (Why is no real title available?)
• Improved algorithms for even factors and square-free simple \(b\)-matchings
• Matching, matroids, and extensions
• Maximum matching and a polyhedron with 0,1-vertices
• Odd Minimum Cut Sets and b-Matchings Revisited
• Odd Minimum Cut-Sets and b-Matchings
• On Maximum Cost $K_{t,t}$‐Free t‐Matchings of Bipartite Graphs
• Perfect triangle-free 2-matchings
• Polyhedron of triangle-free simple 2-matchings in subcubic graphs
• Restricted b-matchings in degree-bounded graphs
• Restricted \(t\)-matchings in bipartite graphs
• Triangle-free 2-matchings and M-concave functions on jump systems
• Weighted triangle-free 2-matching problem with edge-disjoint forbidden triangles

Cited in

(7)

• scientific article; zbMATH DE number 4062620 (Why is no real title available?)
• 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
• Triangle-Free Simple 2-Matchings in Subcubic Graphs (Extended Abstract)
• Finding triangle-free 2-factors in general graphs
• An approximation algorithm for two-edge-connected subgraph problem via triangle-free two-edge-cover
• Finding a maximum restricted \(t\)-matching via Boolean edge-CSP

This page was built for publication: Weighted triangle-free 2-matching problem with edge-disjoint forbidden triangles

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