KIT | KIT-Bibliothek | Impressum | Datenschutz

Graph-based system configuration

Moldenhauer, Horst

Abstract:

We present an optimization problem that arises in the context of
system-design and the refinement of high-level specifications.
We present a graph-based formalization of the problem, thus defining
a new optimization problem, which we call MINIMUM CONFIGURATION.
We prove MINIMUM CONFIGURATION to be NP-hard and also hard to
approximate, i.e. not to be in APX. These results are obtained by
reduction from graph coloring and SHORTEST PATH WITH FORBIDDEN PAIRS.
We show how to apply the introduced concepts to the application
domain and propose a way to identify subclasses in the input space,
for which MINIMUM CONFIGURATION can be solved efficiently.


Volltext §
DOI: 10.5445/IR/17696
Cover der Publikation
Zugehörige Institution(en) am KIT Institut für Programmstrukturen und Datenorganisation (IPD)
Publikationstyp Buch
Publikationsjahr 1996
Sprache Englisch
Identifikator urn:nbn:de:swb:90-AAA176965
KITopen-ID: 17696
Erscheinungsvermerk Karlsruhe 1996. (Interner Bericht. Fakultät für Informatik, Universität Karlsruhe. 1996,20.)
KIT – Die Forschungsuniversität in der Helmholtz-Gemeinschaft
KITopen Landing Page