Hostname: page-component-cd9895bd7-hc48f Total loading time: 0 Render date: 2024-12-27T19:15:11.417Z Has data issue: false hasContentIssue false
  • English
  • Français

A polynomial algorithm for minDSCon a subclass of series Parallel graphs

Published online by Cambridge University Press:  28 April 2009

Salim Achouri ,
Timothée Bossart  and
Alix Munier-Kordon
Salim Achouri
Affiliation:
LIP6 - Université Pierre et Marie Curie, 4 place Jussieu, 75252 Paris Cedex 05, France; [email protected]
Timothée Bossart
Affiliation:
LIP6 - Université Pierre et Marie Curie, 4 place Jussieu, 75252 Paris Cedex 05, France; [email protected]
Alix Munier-Kordon
Affiliation:
LIP6 - Université Pierre et Marie Curie, 4 place Jussieu, 75252 Paris Cedex 05, France; [email protected]
Get access

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.

Keywords

Minimum directed sumcutseries parallel graphpolynomial algorithm.
Type
Research Article
Information
RAIRO - Operations Research , Volume 43 , Issue 2 , April 2009 , pp. 145 - 156
Copyright
© EDP Sciences, ROADEF, SMAI, 2009

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Bossart, T., Munier, A. and Sourd, F., Two models for the optimization of integrated circuit simulators. Discrete Appl. Math. 155 (2007) 1795–1811. CrossRef
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).
Sethi, R., Complete register allocation problems. SIAM J. Computing 4 (1975) 226–248. CrossRef
Smith, W.E., Various optimizers for single stage production. Naval Research Logistics Quarterly 3 (1956) 59–66. CrossRef
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.