No label defined (Q4723312)

From MaRDI portal

!

This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:

scientific article; zbMATH DE number 3997175
Language Label Description Also known as
default for all languages
No label defined
    English
    No label defined
    scientific article; zbMATH DE number 3997175

      Statements

      0 references
      1985
      0 references
      acyclic digraph
      0 references
      backtrack algorithm
      0 references
      parallel algorithm
      0 references
      [For the entire collection see Zbl 0587.00006.] We consider the following decision problem (DP): given the acyclic digraph \(G=(V,A)\) and the positive integers M, W and w(v), \(v\in V\), find a partition \(Q=\{Q_ i\}^ m_{i=1}\) of V so that (i) if (a,b)\(\in A\), \(a\in Q_ r\) and \(b\in Q_ s\) then \(R\leq s\), (ii) \(\sum_{v\in Q_ j}w(v)\leq W\), \(1\leq j\leq m\), and (iii) \(m\leq M\). In order to solve this NP-complete problem a backtrack algorithm is given. For solving the optimization problem (OP), concerning the minimization of m subject to (i) and (ii), we propose an asynchronous parallel algorithm based on a master-slave processing network. By using a tree organization of the solution space, many slave processors (SP) executing the same backtrack algorithm act simultaneously on disjoint subtrees. Each SP sends the obtained partition to the master processor which requires to all SPs to find a better partition. The OP is solved through a sequence of DPs for decreasing values of M. We propose some ways to compute lower and upper bounds for M in order to accelerate the search.
      0 references

      Identifiers

      0 references
      0 references
      0 references
      0 references