Continuous reductions among combinatorial optimization problems

DOI10.1007/BF00289161MaRDI QIDQ1112622zbMATH OpenFDO

Authors Hans Ulrich Simon

Publication date 1989

Published in Acta Informatica (Search for Journal in Brave)

zbMATH Keywords

combinatorial optimizationapproximation algorithmlogic synthesisNP- completenesscombinatorial circuitscontinuous reductions

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Combinatorial optimization (90C27) Applications of graph theory to circuits and networks (94C15) Algorithms in computer science (68W99)

Recommendations

• On Approximate Solutions for Combinatorial Optimization Problems
• Approximation preserving reductions
• scientific article; zbMATH DE number 915981
• Autour de nouvelles notions pour l'analyse des algorithmes d'approximation : de la structure de NPO à la structure des instances
• Reductions, completeness and the hardness of approximability

Cites work

• scientific article; zbMATH DE number 3902554 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 3895002 (Why is no real title available?)
• An Efficient Heuristic Procedure for Partitioning Graphs

Cited in

(2)

• A reduction approach to the repeated assignment problem
• Max NP-completeness made easy

This page was built for publication: Continuous reductions among combinatorial optimization problems

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