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

Abstract

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

How to cite

top

Achouri, 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
  1. 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
  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).  Zbl0839.90059
  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.  
  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. Computing4 (1975) 226–248.  Zbl0327.68042
  7. W.E. Smith, Various optimizers for single stage production. Naval Research Logistics Quarterly3 (1956) 59–66.  
  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.  

NotesEmbed ?

top

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

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.