Even factors, jump systems, and discrete convexity

DOI10.1016/j.jctb.2008.05.001zbMath1247.05052OpenAlexW1968865391MaRDI QIDQ2519019

Yusuke Kobayashi, Kenjiro Takazawa

Publication date: 21 January 2009

Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jctb.2008.05.001

zbMATH Keywords

degree sequenceeven factordelta-matroidjump system\(M\)-convex functionodd-cycle-symmetric digraphvaluated delta-matroid

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Combinatorial aspects of matroids and geometric lattices (05B35) Directed graphs (digraphs), tournaments (05C20)

Related Items (12)

Excluded $t$-Factors in Bipartite Graphs: Unified Framework for Nonbipartite Matchings, Restricted 2-Matchings, and Matroids ⋮ Triangle-free 2-matchings and M-concave functions on jump systems ⋮ Improved algorithms for even factors and square-free simple \(b\)-matchings ⋮ An algorithm for \((n-3)\)-connectivity augmentation problem: jump system approach ⋮ 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 ⋮ An algorithm for finding a maximum \(t\)-matching excluding complete partite subgraphs ⋮ A note on M-convex functions on jump systems ⋮ A survey of fundamental operations on discrete convex functions of various kinds ⋮ On basic operations related to network induction of discrete convex functions

Cites Work

• Unnamed Item
• Unnamed Item
• On the maximum even factor in weakly symmetric graphs
• Convexity and Steinitz's exchange property
• Combinatorial algorithms for matchings, even factors and square-free 2-factors
• Valuated matroids: A new look at the greedy algorithm
• \(\Delta\)-matroid and jump system
• A weighted even factor algorithm
• Some combinatorial properties of discriminants in metric vector spaces
• Pseudomatroids
• A greedy-algorithm characterization of valuated \(\Delta\)-matroids
• Valuated matroids
• The optimal path-matching problem
• \(\Delta\)-matroids with the strong exchange conditions
• The membership problem in jump systems
• Pfaffian forms and \(\Delta\)-matroids
• Matching, matroids, and extensions
• Finding optimal minors of valuated bimatroids
• Submodular functions and optimization.
• On minimal strong blocks
• Matroid Intersection
• Polynomial-Time Algorithms for Linear and Convex Optimization on Jump Systems
• Algebraic Algorithms for Matching and Matroid Problems
• A Combinatorial Algorithm to Find a Maximum Even Factor
• Greedy algorithm and symmetric matroids
• Matroid intersection algorithms
• Discrete Convex Analysis
• Delta-Matroids, Jump Systems, and Bisubmodular Polyhedra
• Paths, Trees, and Flowers
• 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

This page was built for publication: Even factors, jump systems, and discrete convexity