ISSN:
1436-5057
Keywords:
5.32
;
5.41
;
8.3
;
Adjacent set
;
branch-and-bound structure
;
combinatorial programming
;
depthfirst search
;
discrete optimization
;
essential block
;
expansion tree
;
optimal network partitioning
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
Description / Table of Contents:
Zusammenfassung Diese Arbeit befaßt sich mit dem Problem der Zerlegung eines endlichen, zusammenhängenden, schlichten Graphen (Netz genannt) mit gewichteten Knoten und Kanten unter der Randbedingung, daß die Summe der Knotengewichte jedes einzelnen Teilgraphen eine vorgegebene Schranke nicht überschreitet. Gesucht ist die Menge der disjunkten Teilgraphen, welche ein minimales Gesamtgewicht der Kanten zwischen den Teilgraphen besitzt und die Randbedingung erfüllt. Ein neues Rechenverfahren zur Lösung dieses Problems wird vorgestellt, das in der Lage ist, mit vertrebarem Rechenaufwand große Netze optimal zu zerlegen. Auf dem Konzept „Teile und herrsche” beruhend, wird das Problem in mehrere Teilprobleme zerlegt, die nacheinander mittels „depth-first search” und „branch-and-bound” gelöst werden. Die wesentlichen Rechenschritte bestehen aus Additionen, Vergleichen, und logischen Verknüpfungen von booleschen Vektoren.
Notes:
Abstract The problem considered is to partition an edge-valued, node-weighted, finite, connected, simple graph (called a network) into disjoint subgraphs, each of which has a total node weight that does not exceed a weight constraint, and so that the total value of edges interconnecting the subgraphs is minimized. This paper presents a new approach which is effective in solving the problem, and fast enough to be practical in finding optimal partitions of large networks. It uses the concept of “divide and conquer” to partition the problem into several subproblems, which can be efficiently solved one after the other by using depth-first search and branch-and-bound principle. The operations required under the algorithms are additions, comparisons, and logical operations on binary vectors.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF02241700
Permalink
