Constrained matroidal bottleneck problems

DOI10.1016/0166-218X(95)00114-4MaRDI QIDQ1917230zbMATH OpenFDO

Authors Igor Averbakh, Oded Berman, Abraham P. Punnen

Publication date 29 September 1996

Published in Discrete Applied Mathematics (Search for Journal in Brave)

zbMATH Keywords

algorithmscomplexityuniform matroidsassignment and scheduling problemsconstrained bottleneck independent set problemconstrained bottleneck matroid base problemmatroidal problemsproblems on partition

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Combinatorial aspects of matroids and geometric lattices (05B35)

Recommendations

• A constrained independent set problem for matroids
• k-Best constrained bases of a matroid
• A matroid algorithm and its application to the efficient solution of two optimization problems on graphs
• Generalized Bottleneck Problems^∗

Cites work

• scientific article; zbMATH DE number 3511563 (Why is no real title available?)
• scientific article; zbMATH DE number 3534506 (Why is no real title available?)
• scientific article; zbMATH DE number 3558962 (Why is no real title available?)
• scientific article; zbMATH DE number 3793772 (Why is no real title available?)
• An Improved Algorithm for the Constrained Bottleneck Spanning Tree Problem
• Efficient algorithms for finding minimum spanning trees in undirected and directed graphs
• The Constrained Bottleneck Problem in Networks
• The Min-Max Spanning Tree Problem and some extensions
• The matroidal knapsack: A class of (often) well-solvable problems

Cited in

(8)

• k-Best constrained bases of a matroid
• A multiply constrained matroid optimization problem
• A constrained independent set problem for matroids
• Trapezoidal matrices and the bottleneck assignment problem
• A cooperative local search-based algorithm for the multiple-scenario max-min knapsack problem
• An Oracle Strongly Polynomial Algorithm for Bottleneck Expansion Problems
• On discrete optimization with ordering
• A class of bottleneck expansion problems

This page was built for publication: Constrained matroidal bottleneck problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1917230)