Adjacency on polymatroids

DOI10.1007/BF02591887zbMath0544.90077MaRDI QIDQ3335528

Donald M. Topkis

Publication date: 1984

Published in: Mathematical Programming (Search for Journal in Brave)

zbMATH Keywords

submodular functionpolynomial algorithmpolymatroidconvex gameadjacency for extreme points

Mathematics Subject Classification ID

Integer programming (90C10) Combinatorial aspects of matroids and geometric lattices (05B35) Polytopes and polyhedra (52Bxx)

Related Items

Generalized polymatroids and submodular flows, Extended formulations for matroid polytopes through randomized protocols, On the expansion of combinatorial polytopes, Circuit walks in integral polyhedra, The fundamental theorem of linear programming: extensions and applications, Two algorithms for maximizing a separable concave function over a polymatroid feasible region, Paths on polymatroids, Ehrhart polynomials of matroid polytopes and polymatroids, The polytope of win vectors, A note on Frank's generalized polymatroids, On the Length of Monotone Paths in Polyhedra

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Characterizations of adjacency on the branching polyhedron
• Adjacent vertices on the b-matching polyhedron
• The ellipsoid method and its consequences in combinatorial optimization
• On certain polytopes associated with graphs
• Cores of convex games
• The Partial Order of a Polymatroid Extreme Point
• Adjacency on the Postman Polyhedron
• Adjacent vertices on transportation polytopes
• The travelling salesman problem and a class of polyhedra of diameter two
• On the Set-Covering Problem: II. An Algorithm for Set Partitioning
• Adjacency of the Traveling Salesman Tours and $0 - 1$ Vertices
• Determining adjacent vertices on assignment polytopes
• Adjacent Vertices on a Permutohedron
• The adjacency relation on the traveling salesman polytope is NP-Complete
• ALGORITHMS FOR SOLVING THE INDEPENDENT-FLOW PROBLEMS
• Adjacent vertices of the all 0-1 programming polytope
• Activity selection games and the minimum‐cut problem
• On the Tours of a Traveling Salesman
• Adjacency on Convex Polyhedra
• Some properties of the assignment polytope
• On the Set-Covering Problem