# A polynomial algorithm for minDSC on a subclass of series Parallel graphs

Salim Achouri; Timothée Bossart; Alix Munier-Kordon

RAIRO - Operations Research (2009)

- Volume: 43, Issue: 2, page 145-156
- ISSN: 0399-0559

## Access Full Article

top## Abstract

top## How to cite

topAchouri, Salim, Bossart, Timothée, and Munier-Kordon, Alix. "A polynomial algorithm for minDSC on a subclass of series Parallel graphs." RAIRO - Operations Research 43.2 (2009): 145-156. <http://eudml.org/doc/250549>.

@article{Achouri2009,

abstract = {
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.
},

author = {Achouri, Salim, Bossart, Timothée, Munier-Kordon, Alix},

journal = {RAIRO - Operations Research},

keywords = {Minimum directed sumcut; series parallel graph; polynomial algorithm.; minimum directed sumcut; polynomial algorithm},

language = {eng},

month = {4},

number = {2},

pages = {145-156},

publisher = {EDP Sciences},

title = {A polynomial algorithm for minDSC on a subclass of series Parallel graphs},

url = {http://eudml.org/doc/250549},

volume = {43},

year = {2009},

}

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

DA - 2009/4//

PB - EDP Sciences

VL - 43

IS - 2

SP - 145

EP - 156

AB -
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.

LA - eng

KW - Minimum directed sumcut; series parallel graph; polynomial algorithm.; minimum directed sumcut; polynomial algorithm

UR - http://eudml.org/doc/250549

ER -

## References

top- T. Bossart, A. Munier and F. Sourd, Two models for the optimization of integrated circuit simulators. Discrete Appl. Math.155 (2007) 1795–1811. Zbl1144.94391
- T. Bossart, Optimisation de la mémoire cache pour la simulation de circuits. Ph.D. thesis, Université Pierre et Marie Curie (2006).
- P. Brucker, Scheduling Algorithms. Springer-Verlag New York, Inc., Secaucus, NJ, USA (1995). Zbl0839.90059
- 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.
- L.A.M. Schoenmakers, A new algorithm for the recognition of series parallel graphs, Technical Report CS-R9504 Centrum voor Wiskunde en Informatica (1995).
- R. Sethi, Complete register allocation problems. SIAM J. Computing4 (1975) 226–248. Zbl0327.68042
- W.E. Smith, Various optimizers for single stage production. Naval Research Logistics Quarterly3 (1956) 59–66.
- 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.

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.