A polynomial algorithm for minDSC on a subclass of series parallel graphs
RAIRO - Operations Research - Recherche Opérationnelle, Tome 43 (2009) no. 2, pp. 145-156.

The aim of this paper is to show a polynomial algorithm for the problem minimum directed sumcut for a class of series parallel digraphs. The method uses the recursive structure of parallel compositions in order to define a dominating set of orders. Then, the optimal order is easily reached by minimizing the directed sumcut. It is also shown that this approach cannot be applied in two more general classes of series parallel digraphs.

DOI : 10.1051/ro/2009009
Classification : 05C78, 05C85, 90B35
Mots-clés : minimum directed sumcut, series parallel graph, polynomial algorithm 
@article{RO_2009__43_2_145_0,
     author = {Achouri, Salim and Bossart, Timoth\'ee and Munier-Kordon, Alix},
     title = {A polynomial algorithm for {minDSC} on a subclass of series parallel graphs},
     journal = {RAIRO - Operations Research - Recherche Op\'erationnelle},
     pages = {145--156},
     publisher = {EDP-Sciences},
     volume = {43},
     number = {2},
     year = {2009},
     doi = {10.1051/ro/2009009},
     mrnumber = {2527860},
     zbl = {1162.05349},
     language = {en},
     url = {http://archive.numdam.org/articles/10.1051/ro/2009009/}
}
TY  - JOUR
AU  - Achouri, Salim
AU  - Bossart, Timothée
AU  - Munier-Kordon, Alix
TI  - A polynomial algorithm for minDSC on a subclass of series parallel graphs
JO  - RAIRO - Operations Research - Recherche Opérationnelle
PY  - 2009
SP  - 145
EP  - 156
VL  - 43
IS  - 2
PB  - EDP-Sciences
UR  - http://archive.numdam.org/articles/10.1051/ro/2009009/
DO  - 10.1051/ro/2009009
LA  - en
ID  - RO_2009__43_2_145_0
ER  - 
%0 Journal Article
%A Achouri, Salim
%A Bossart, Timothée
%A Munier-Kordon, Alix
%T A polynomial algorithm for minDSC on a subclass of series parallel graphs
%J RAIRO - Operations Research - Recherche Opérationnelle
%D 2009
%P 145-156
%V 43
%N 2
%I EDP-Sciences
%U http://archive.numdam.org/articles/10.1051/ro/2009009/
%R 10.1051/ro/2009009
%G en
%F RO_2009__43_2_145_0
Achouri, Salim; Bossart, Timothée; Munier-Kordon, Alix. A polynomial algorithm for minDSC on a subclass of series parallel graphs. RAIRO - Operations Research - Recherche Opérationnelle, Tome 43 (2009) no. 2, pp. 145-156. doi : 10.1051/ro/2009009. http://archive.numdam.org/articles/10.1051/ro/2009009/

[1] T. Bossart, A. Munier and F. Sourd, Two models for the optimization of integrated circuit simulators. Discrete Appl. Math. 155 (2007) 1795-1811. | MR | Zbl

[2] T. Bossart, Optimisation de la mémoire cache pour la simulation de circuits. Ph.D. thesis, Université Pierre et Marie Curie (2006).

[3] P. Brucker, Scheduling Algorithms. Springer-Verlag New York, Inc., Secaucus, NJ, USA (1995). | Zbl

[4] P. Chrétienne and C. Picouleau, Scheduling with communication delays: a survey, in Scheduling Theory and its Applications, edited by P. Chretienne, E.G. Jr Coffman, J.K. Lenstra and Z. Liu, Chap. 4. John Wiley & Sons (1995) 65-90. | MR

[5] L.A.M. Schoenmakers, A new algorithm for the recognition of series parallel graphs, Technical Report CS-R9504 Centrum voor Wiskunde en Informatica (1995).

[6] R. Sethi, Complete register allocation problems. SIAM J. Computing 4 (1975) 226-248. | MR | Zbl

[7] W.E. Smith, Various optimizers for single stage production. Naval Research Logistics Quarterly 3 (1956) 59-66. | MR

[8] J. Valdes, R.E. Tarjan and E.L. Lawler, The recognition of series parallel digraphs, in Proceedings of the eleventh annual ACM symposium on Theory of computing. ACM Press (1979) 1-12. | MR

Cité par Sources :