The cardinality and precedence constrained maximum value sub-hypergraph problem and its applications

DOI10.1016/S0166-218X(96)00015-7MaRDI QIDQ678869zbMATH OpenFDO

Authors David Nehme, Gang Yu

Publication date 29 May 1997

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

Full work available at URL http://www.elsevier.com/locate/dam

zbMATH Keywords

dynamic programminghyperedgeshypergraphpolynomial-time algorithm

Mathematics Subject Classification ID

Hypergraphs (05C65) Graph theory (including graph drawing) in computer science (68R10) Dynamic programming (90C39)

Recommendations

• Computing partial hypergraphs of bounded width
• On the structure of linear programs with overlapping cardinality constraints
• The complexity of finding arborescences in hypergraphs
• Solution of one problem of optimal partition of the vertex set of a hypergraph

Cites work

• A Selection Problem of Shared Fixed Costs and Network Flows
• A strongly polynomial minimum cost circulation algorithm
• Exact Algorithms For The Setup Knapsack Problem
• scientific article; zbMATH DE number 44282 (Why is no real title available?)
• scientific article; zbMATH DE number 698819 (Why is no real title available?)
• Models Arising from a Flexible Manufacturing Machine, Part II: Minimization of the Number of Switching Instants
• On Knapsacks, Partitions, and a New Dynamic Programming Technique for Trees
• OPTIMAL TOOL MODULE DESIGN PROBLEM FOR NC MACHINE TOOLS
• Polyhedral results for the precedence-constrained knapsack problem

Cited in

(2)

• An annotated bibliography of combinatorial optimization problems with fixed cardinality constraints
• The complexity of detecting fixed-density clusters

This page was built for publication: The cardinality and precedence constrained maximum value sub-hypergraph problem and its applications

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