ISSN:
1432-5217
Keywords:
Quadratic assignment problems
;
series-parallel digraphs
Source:
Springer Online Journal Archives 1860-2000
Topics:
Mathematics
,
Economics
Description / Table of Contents:
Zusammenfassung Christofides hat gezeigt, daß das quadratische Zuordnungsproblem (QZP) auf isomorphen Bäumen polynomial lösbar ist. Der Ansatz von Christofides wird auf minimale serienparallele Digraphen verallgemeinert, und es wird gezeigt, daß das resultierende QZP äquivalent zum allgemeinen QZP ist, also NP-schwer. Die Einschränkung des Problems auf diejenigen serien-parallelen Digraphen, die keine bipartiten Teilgraphen enthalten, ist wieder polynomial lösbar. Dafür wird ein Algorithmus angegeben.
Notes:
Abstract Christofides has shown that the quadratic assignment problem (QAP) on isomorphic trees is solvable in polynomial time by dynamic programming. We generalize the approach to minimal series-parallel digraphs and show that this problem is equivalent to the general QAP, thus NP-hard. However the restriction to the subclass of series-parallel digraphs not containing bipartite subgraphs again is solvable in polynomial time. An algorithm for this class is given.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF01919179
