Scheduling Interval-Ordered Tasks | Zendy

Christos H. Papadimitriou | Zendy; Mihalis Yannakakis | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Open Access

Scheduling Interval-Ordered Tasks

Author(s) -

Christos H. Papadimitriou,

Mihalis Yannakakis

Publication year - 1979

Publication title -

siam journal on computing

Language(s) - English

Resource type - Journals

SCImago Journal Rank - 1.533

H-Index - 122

eISSN - 1095-7111

pISSN - 0097-5397

DOI - 10.1137/0208031

Subject(s) - scheduling (production processes) , computer science , interval graph , chordal graph , interval (graph theory) , parallel computing , complement (music) , constraint (computer aided design) , execution time , combinatorics , mathematics , discrete mathematics , mathematical optimization , theoretical computer science , graph , biochemistry , chemistry , geometry , 1 planar graph , complementation , gene , phenotype

We show that unit execution time jobs subject to a precedence constraint whose complement is chordal can be scheduled in linear time on m processors. Generalizations to arbitrary execution times are NP-complete.

The content you want is available to Zendy users.

Already have an account? Click here to sign in.

Having issues? You can contact us here

Accelerating Research