The image of weighted combinatorial problems

DOI10.1007/BF02115754zbMath0747.90082MaRDI QIDQ1179736

Paolo M. Camerini, Francesco Maffioli, Giulia Galbiati

Publication date: 27 June 1992

Published in: Annals of Operations Research (Search for Journal in Brave)

zbMATH Keywords

image of weighted combinatorial problemsmatroid parity bases

Mathematics Subject Classification ID

Abstract computational complexity for mathematical programming problems (90C60) Combinatorial optimization (90C27)

Related Items

Cardinality constrained minimum cut problems: complexity and algorithms. ⋮ Random pseudo-polynomial algorithms for some combinatorial programming problems

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Balanced optimization problems
• Most and least uniform spanning trees
• Exact arborescences, matchings and cycles
• Matching is as easy as matrix inversion
• On the complexity of finding multi-constrained spanning trees
• The Min-Max Spanning Tree Problem and some extensions
• Intersection of Two Matroids: (Condensed) Border Graphs and Ranking
• Fast Probabilistic Algorithms for Verification of Polynomial Identities
• Random pseudo-polynomial algorithms for exact matroid problems
• Systems of distinct representatives and linear algebra
• Matroids and the greedy algorithm
• The Factorization of Linear Graphs