Games and graphs

游戏和图表

• 批准号: 4820-2009
• 负责人: Nowakowski, Richard
• 金额: $ 2.04万
• 依托单位: Dalhousie University
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2012
• 资助国家: 加拿大
• 起止时间: 2012-01-01 至 2013-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=503784
• 关键词: Games; graphs

Well-covered graphs: Divide-and-conquer is a well-tried and useful approach to hard problems. On the other hand, well-covered graphs have the property that hard problems (like scheduling jobs or examinations) are easy: the hard part is recognizing when a graph is well-covered. A labeling approach based on recognizing when two `jobs' cannot be scheduled at the same time partitions the graph into well-covered subgraphs that allows an easy but good starting point from which to schedule all the `jobs'.

覆盖良好的图：分而治之是解决难题的一种行之有效的方法。另一方面，良好覆盖图具有困难问题（如安排作业或考试）很容易的属性：困难的部分是识别图何时被良好覆盖。一个标签的基础上认识到当两个“工作”不能在同一时间安排分区的图形到覆盖良好的子图，允许一个简单的，但良好的起点，从调度所有的“工作”。