Triangle-free 2-matchings and M-concave functions on jump systems

DOI10.1016/j.dam.2014.05.016zbMath1298.05264OpenAlexW2049544856MaRDI QIDQ401132

Yusuke Kobayashi

Publication date: 26 August 2014

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2014.05.016

zbMATH Keywords

degree sequencejump systemM-concave functiontriangle-free 2-matching

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Vertex degrees (05C07)

Related Items

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 fast scaling algorithm for the weighted triangle-free 2-matching problem, Decomposition Theorems for Square-free 2-matchings in Bipartite Graphs, Weighted triangle-free 2-matching problem with edge-disjoint forbidden triangles

Cites Work

• 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
• A matching problem with side conditions
• The membership problem in jump systems
• Restricted \(t\)-matchings in bipartite graphs
• Matching, matroids, and extensions
• Even factors, jump systems, and discrete convexity
• Polynomial-Time Algorithms for Linear and Convex Optimization on Jump Systems
• Delta-Matroids, Jump Systems, and Bisubmodular Polyhedra
• Operations on M‐Convex Functions on Jump Systems
• M-Convex Functions on Jump Systems: A General Framework for Minsquare Graph Factor Problem
• Integer Programming and Combinatorial Optimization