本档案包含特拉维夫大学计算机科学系Ron Shamir教授的”图形算法中的高级课题”课程的资料，时间为10/91-2/92（92年秋季）、4-6/94（94年春季）和4-6/97（97年春季）。这是一门为期一学期的研究生课程，也对高年级学生开放，每周开一次三小时的会议。
本课程强调了”好的”图族的算法和结构方面，特别是完美图、区间图、弦图和比较图。在92年秋季，该课程在很大程度上是基于马丁C.戈伦比的经典著作《算法图论与完美图》（学术出版社，1980）为基础的，在某些部分还以道格拉斯B.韦斯特的手稿《组合数学的艺术》为基础的。“94年春季”和“97年春季”课程的基础相似，但强调的是较新的材料，并对分子生物学的应用做了大量的参考。（关于这些方面的更多信息，请参阅网页”分子生物学算法“）。
可用材料:
- 详细的课程大纲
- 1997年春季课程材料（无组织；某些链接未更新，某些材料仅有TAU浏览器可读。抱歉。）
您可以下载完整的笔记作为一个单独的PostScript文件（150页），也可单独下载每个讲座。
有关其他语言的课堂讲稿的翻译，请参阅此处。
- 封面页
- 目录
- 数字一览表
讲座一：图论导论
- 基本定义和符号
- 相交图
- 圆弧图
- 区间图
- 二部图的线图
讲座2：完美图形
- 完美图的定义
- 一些定义和属性
- 完全图定理
讲座3：完美和三角图
O 完美图形
- $p$-关键图
- 完全图的多面体特征
- 强完全图猜想
- 三角图
- 介绍
- 三角图的特征化
- 三角图的识别
- 时间复杂性
讲座4：三角图的识别
o识别三角图
- 生成PEO
- 测试排除方案
- 朴素算法
- 高效算法
- 例子
- 算法的正确性
- 算法的复杂性
- 三角图作为交叉图
- 进化树
- 三角图作为交叉图
讲座5：三角图是完美的
o三角图是完美的
- 证明这一性质
- 其它结果
- 计算最小填充量
- 问题
- 填充是NP-难的。
- 链图
- 最优线性排列（OLA）
- 链图完成（CGC）
- 填写结果
- 问题
讲座6：三角图和可比图的算法
- 三角图的若干优化算法
- 色数和所有极大群的计算
- 查找$\alpha$和$k$
- 比较图
- 一些定义
- 蕴涵类
- 三角引理
- 图的分解
讲座7：唯一部分可排序图
- 唯一部分可序图
- 特征和识别算法
讲座8：一些有趣的以交叉为特征的图形族
- 简介
- 置换图
- $F$-图
- “空中管制员罢工”
- 排列图的合成
- 容差图
- 作为容差图的子集的区间图
- 有界和无界容差图
讲座9：可比性图
- 相似性图形识别
- 相似性图识别的复杂性
- 实施
- 复杂性分析
- 关于比较图的着色及其它问题
- 可比较性图是完美的
- 最大加权团
- 计算$\alpha（g）$
- 偏序维数
讲座10：可比性不变量和区间图
- 相似性不变量
- 区间图
讲座11：区间图
- 偏好与冷漠
- 区间图识别
- 一种二次算法
- 线性算法
- 有关连续1s属性的更多信息
讲座12：时间推理
- 时间推理与区间代数
- 区间可满足性问题
- 区间夹层问题与ISAT
- ISAT（$\Delta_1}$）的线性时间算法
- 带宽、路径宽度和适当路径宽度
请将所有反馈和意见发送至: rshamir@tau.ac.il