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
1985
0 references
acyclic digraph
0 references
backtrack algorithm
0 references
parallel algorithm
0 references
0.92127526
0 references
0.92127526
0 references
0.9198572
0 references
0.9119394
0 references
0.9096111
0 references
0.9086137
0 references
0.89439404
0 references
0.8939548
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