作者:A.萨拉查，R. V.奥克福德
ACM通信，1974年12月，第17卷第12期，第696-698页
10.1145/361604.361625
评论
经典的题目“考试时间表问题”在文献中有多种形式。这些公式中的大多数都可以用经典网络理论的术语来表示。一个这样的公式是:给定一个无向网络，将它的节点划分为最小数量的子集，这样同一个子集中的两个成员就不会被圆弧连接。
这个数的一个明显的下限是最大的强连通子图的大小。Kirchgassner证明了上限是这个大小加1。
对前面工作的一个逻辑扩展是引入变长考试，其中W(I)是考试I的课时数。本文的目的是推广最大强连通子图的定义，包括节点的权重，提出一个通常寻找最大强连通子图的近似算法，并讨论该算法在解决学校调度和考试调度问题中的应用。
本文的全文是优质内容
没有发现记录
登录阅读全文
需要访问吗?
请选择下面的一个选项以访问高级内容和功能。
创建一个网上帐户
如果你已经是ACM会员，通信订阅者或数码图书馆订阅者，请设置网页帐户，以浏览本网站的优质内容。
参加ACM
成为ACM的会员，可以充分利用ACM卓越的计算信息资源、网络机会等优势。
订阅ACM杂志通讯
获得50多年的中华中医药学会内容的完整访问权限，并每月获得杂志印刷版。
购买这篇文章
非会员可以购买这篇文章或刊登这篇文章的杂志。
