M-Convex Functions on Jump Systems: A General Framework for Minsquare Graph Factor Problem

DOI10.1137/040618710zbMath1119.90031OpenAlexW2079530391MaRDI QIDQ5470828

Kazuo Murota

Publication date: 1 June 2006

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

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

zbMATH Keywords

degree sequencelocal optimalityjump systemdiscrete convex functiongraph factor

Mathematics Subject Classification ID

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

Related Items (20)

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 ⋮ Triangle-free 2-matchings and M-concave functions on jump systems ⋮ Optimal general factor problem and jump system intersection ⋮ An algorithm for \((n-3)\)-connectivity augmentation problem: jump system approach ⋮ Geodesic property of greedy algorithms for optimization problems on jump systems and delta-matroids ⋮ A weighted independent even factor algorithm ⋮ A simple algorithm for finding a maximum triangle-free \(2\)-matching in subcubic graphs ⋮ Recent Developments in Discrete Convex Analysis ⋮ A proof of Cunningham's conjecture on restricted subgraphs and jump systems ⋮ Isotropical linear spaces and valuated Delta-matroids ⋮ A note on M-convex functions on jump systems ⋮ Induction of M-convex functions by linking systems ⋮ Even factors, jump systems, and discrete convexity ⋮ Decomposition Theorems for Square-free 2-matchings in Bipartite Graphs ⋮ A survey of fundamental operations on discrete convex functions of various kinds ⋮ On basic operations related to network induction of discrete convex functions ⋮ Discrete Concavity and Zeros of Polynomials ⋮ Bisubmodular polyhedra, simplicial divisions, and discrete convexity ⋮ Minconvex graph factors of prescribed size and a simpler reduction to weighted f-factors

This page was built for publication: M-Convex Functions on Jump Systems: A General Framework for Minsquare Graph Factor Problem