Combinatorial problems over power sets

DOI10.1007/BF02576644zbMath0442.90106MaRDI QIDQ1143948

Marco Protasi, Alberto Marchetti-Spaccamela, Giorgio Ausiello

Publication date: 1979

Published in: Calcolo (Search for Journal in Brave)

zbMATH Keywords

NP-complete optimization problemscombinatorial problems over power setsstructure of a combinatorial problemstructure preserving reductions

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Mathematical programming (90C99)

Related Items

Relative complexity of evaluating the optimum cost and constructing the optimum for maximization problems

Cites Work

• The complexity of computing the permanent
• Structure preserving reductions among convex optimization problems
• The Complexity of Enumeration and Reliability Problems
• The Effect of a Connectivity Requirement on the Complexity of Maximum Subgraph Problems
• Node-Deletion NP-Complete Problems
• On the complexity of the Maximum Subgraph Problem
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item