A POLYNOMIAL ALGORITHM FOR MINDSC ON A SUBCLASS OF SERIES PARALLEL GRAPHS

被引：3

作者：

Achouri, Salim ^{[1
]}

Bossart, Timothee ^{[1
]}

Munier-Kordon, Alix ^{[1
]}

机构：

[1] Univ Paris 06, LIP6, F-75252 Paris 05, France

来源：

RAIRO-OPERATIONS RESEARCH | 2009年 / 43卷 / 02期

关键词：

Minimum directed sumcut; series parallel graph; polynomial algorithm;

D O I：

10.1051/ro/2009009

中图分类号：

C93 [管理学]; O22 [运筹学];

学科分类号：

070105 ; 12 ; 1201 ; 1202 ; 120202 ;

摘要：

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.

引用

页码：145 / 156

页数：12

共 8 条

[1]

BOSSART T, 2006, THESIS U P M CURIE

[2] Memory management optimization problems for integrated circuit [J].

Bossart, Timothee ;

Kordon, Alix Munier ;

Sourd, Francis .

DISCRETE APPLIED MATHEMATICS, 2007, 155 (14) :1795-1811

[3]

Brucker P., 1995, Scheduling Algorithms

[4]

Chretienne Ph., 1995, SCHEDULING THEORY IT, P65

[5]

SCHOENMAKERS LAM, 1995, CSR9504 CTR WISK INF

[6]

Sethi R., 1975, SIAM Journal on Computing, V4, P226, DOI 10.1137/0204020

[7]

Smith W. E., 1956, Naval Res. Logist. Q., V3, P59, DOI [10.1002/nav.3800030106, DOI 10.1002/NAV.3800030106]

[8]

Valdes J., 1979, Proceedings of the Eleventh Annual ACM Symposium on Theory of Computing, P1

← 1 →