On structures of bisubmodular polyhedra

DOI10.1007/BF02592201zbMath0855.68107OpenAlexW2052875787MaRDI QIDQ1814796

Satoru Fujishige, Kazutoshi Ando

Publication date: 14 January 1997

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

Full work available at URL: https://doi.org/10.1007/bf02592201

zbMATH Keywords

bisubmodular functionbisubmodular polyhedron

Mathematics Subject Classification ID

Abstract computational complexity for mathematical programming problems (90C60) Combinatorial optimization (90C27) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Related Items

Strongly polynomial and fully combinatorial algorithms for bisubmodular function minimization, A polyhedral approach to bisubmodular function minimization, Decomposition of a bidirected graph into strongly connected components and its signed poset structure, Personal reminiscence: combinatorial and discrete optimization problems in which I have been interested, Monotone diameter of bisubmodular polyhedra, Characterizations of the set of integer points in an integral bisubmodular polyhedron, Polyhedra with submodular support functions and their unbalanced simultaneous exchangeability, Bipolarization of posets and natural interpolation, Greedy oriented flows, Polynomial combinatorial algorithms for skew-bisubmodular function minimization, Greedy systems of linear inequalities and lexicographically optimal solutions, Making bidirected graphs strongly connected, Polybasic polyhedra: Structure of polyhedra with edge vectors of support size at most 2, An algorithm for solving the minimum-norm point problem over the intersection of a polytope and an affine set, Signed ring families and signed posets, Generalized skew bisubmodularity: a characterization and a min-max theorem, Bisubmodular polyhedra, simplicial divisions, and discrete convexity, A lexicographic algebraic theorem and its applications, Parametric bisubmodular function minimization and its associated signed ring family

Cites Work

• Unnamed Item
• Unnamed Item
• Matchings and \(\Delta\)-matroids
• Some combinatorial properties of discriminants in metric vector spaces
• Pseudomatroids
• Directed submodularity, ditroids and directed submodular flows
• Submodular functions and optimization
• Signed posets
• On totally dual integral systems
• Decomposition of a bidirected graph into strongly connected components and its signed poset structure
• On the notion of balance of a signed graph
• The Partial Order of a Polymatroid Extreme Point
• Greedy algorithm and symmetric matroids
• A greedy algorithm for solving a certain class of linear programmes
• A Min--Max Theorem for Bisubmodular Polyhedra
• BALANCED BISUBMODULAR SYSTEMS AND BIDIRECTED FLOWS
• Delta-Matroids, Jump Systems, and Bisubmodular Polyhedra