On the complexity of finding even pairs in planar perfect graphs

详细信息    查看全文

• 作者：Rudini M. Sampaio ; Clé ; udia L. Sales
• 关键词：Scheduling ; communication delays ; performance guarantee
• 刊名：Electronic Notes in Discrete Mathematics
• 出版年：2001
• 出版时间：April 2001
• 年：2001
• 卷：7
• 期：Complete
• 页码：186-189
• 全文大小：270 K

文摘

We consider the problem of scheduling a directed acyclic graph on a limited number of processors in presence of communication delays (Pprec, C_ijC_max). Under the small communication time assumption, meaning that the communication delays are smaller than the computation times of the tasks, we propose a new list scheduling algorithm. This algorithm takes advantage of the duplication to reduce the impact of the communications on the schedule makespan. We establish for this algorithm a worst case performance guarantee of 2 compared to an optimal solution.