外平面图的一个多项式时间度量(扩展摘要)A Polynomial-time Metric for Outerplanar Graphs (Extended Abstract) |
|
课程网址: | http://videolectures.net/mlg07_schietgat_aptmfo/ |
主讲教师: | Leander Schietgat |
开课单位: | 鲁汶大学 |
开课时间: | 2007-09-05 |
课程语种: | 英语 |
中文简介: | 在化学信息学的背景下,图已经成为分子表示的非常流行的。然而,许多处理图形的算法计算起来非常昂贵。本文主要研究外平面图,这是一类能代表大多数分子的图。我们在外平面图上定义了一个度量,它是基于找到一个最大公共子图,并且我们提出了一个在多项式时间内运行的算法。对分子有一个有效的可计算度量可以显著提高分子数据库的虚拟筛选。 |
课程简介: | In the chemoinformatics context, graphs have become very popular for the representation of molecules. However, a lot of algorithms handling graphs are computationally very expensive. In this paper we focus on outerplanar graphs, a class of graphs that is able to represent the majority of molecules. We define a metric on outerplanar graphs that is based on finding a maximum common subgraph and we present an algorithm that runs in polynomial time. Having an efficiently computable metric on molecules can improve the virtual screening of molecular databases significantly. |
关 键 词: | 化学信息学; 算法处理图; 外平面图; 多项式时间算法; 分子数据库 |
课程来源: | 视频讲座网 |
最后编审: | 2020-05-29:吴雨秋(课程编辑志愿者) |
阅读次数: | 61 |