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

DOI10.1007/S10107-021-01661-YzbMATH Open1489.90158OpenAlexW2988186967MaRDI QIDQ2118149FDOQ2118149

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

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

zbMATH Keywords

triangle-freepolynomial-time algorithmextended formulationrestricted 2-matching

Mathematics Subject Classification ID

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

Cites Work

• Geometric algorithms and combinatorial optimization
• Maximum matching and a polyhedron with 0,1-vertices
• Extended formulations in combinatorial optimization
• Odd Minimum Cut-Sets and b-Matchings
• A weighted linear matroid parity algorithm
• Odd Minimum Cut Sets and b-Matchings Revisited
• A matching problem with side conditions
• Restricted \(t\)-matchings in bipartite graphs
• Matching, matroids, and extensions
• Triangle-free 2-matchings and M-concave functions on jump systems
• 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
• Finding maximum square-free 2-matchings in bipartite graphs
• A weighted \(K_{t,t}\)-free \(t\)-factor algorithm for bipartite graphs
• On Maximum Cost $K_{t,t}$‐Free t‐Matchings of Bipartite Graphs
• Combinatorial algorithms for matchings, even factors and square-free 2-factors
• Polyhedron of triangle-free simple 2-matchings in subcubic graphs
• Restricted \(b\)-matchings in degree-bounded graphs
• Perfect triangle-free 2-matchings
• Title not available (Why is that?)
• Finding a maximum 2-matching excluding prescribed cycles in bipartite graphs
• Improved algorithms for even factors and square-free simple \(b\)-matchings
• Excluded \(t\)-factors in bipartite graphs: a unified framework for nonbipartite matchings and restricted 2-matchings
• Weighted triangle-free 2-matching problem with edge-disjoint forbidden triangles
• Decomposition theorems for square-free 2-matchings in bipartite graphs

Cited In (5)

• Triangle-Free Simple 2-Matchings in Subcubic Graphs (Extended Abstract)
• Weighted triangle-free 2-matching problem with edge-disjoint forbidden triangles
• Title not available (Why is that?)
• Excluded $t$-Factors in Bipartite Graphs: Unified Framework for Nonbipartite Matchings, Restricted 2-Matchings, and Matroids
• Finding triangle-free 2-factors in general graphs

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)