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
topHow 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.
- 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).
- 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.
- 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 ?
topYou must be logged in to post comments.
To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.