NP-COMPLETENESS PROPERTIES ABOUT LINEAR EXTENSIONS

被引：16

作者：

BOUCHITTE, V

HABIB, M

机构：

[1] ECOLE MINES ST ETIENNE, DEPT INFORMAT APPL, F-42023 ST ETIENNE 2, FRANCE

[2] ECOLE NATL SUPER TELECOMMUN BRETAGNE, DEPT INFORMAT & RESEAUX, COMMUN LAB, F-29285 BREST, FRANCE

[3] UNIV BRETAGNE OCCIDENTALE, COMMUN LAB, F-29279 BREST, FRANCE

来源：

ORDER-A JOURNAL ON THE THEORY OF ORDERED SETS AND ITS APPLICATIONS | 1987年 / 4卷 / 02期

关键词：

D O I：

10.1007/BF00337693

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

引用

页码：143 / 154

页数：12

共 14 条

[1]

[Anonymous], 1971, STOC 71, DOI DOI 10.1145/800157.805047

[2]

BOUCHITTE V, 1986, 5 ENST BRET RAPP REC

[3]

COGIS O, 1979, RAIRO-INF THEOR-TH C, V13, P3

[4] A DECOMPOSITION THEOREM FOR PARTIALLY ORDERED SETS [J].

DILWORTH, RP .

ANNALS OF MATHEMATICS, 1950, 51 (01) :161-166

[5] MINIMIZING SETUPS FOR CYCLE-FREE ORDERED SETS [J].

DUFFUS, D ;

RIVAL, I ;

WINKLER, P .

PROCEEDINGS OF THE AMERICAN MATHEMATICAL SOCIETY, 1982, 85 (04) :509-513

[6] ALGORITHMIC APPROACHES TO SETUP MINIMIZATION [J].

FAIGLE, U ;

GIERZ, G ;

SCHRADER, R .

SIAM JOURNAL ON COMPUTING, 1985, 14 (04) :954-965

[7]

Garey MR., 1979, COMPUTERS INTRACTABI

[8] NP-COMPLETENESS RESULTS CONCERNING GREEDY AND SUPER GREEDY LINEAR EXTENSIONS [J].

KIERSTEAD, HA .

ORDER-A JOURNAL ON THE THEORY OF ORDERED SETS AND ITS APPLICATIONS, 1986, 3 (02) :123-134

[9]

PRETZEL O, 1985, OBERWOLFACH C COMBIN

[10]

PULLEYBLANK WR, IN PRESS DISCRETE MA

← 1 2 →