图 书 馆
Min，Max和PTIME反单调重叠图测量Min, Max and PTIME Anti-Monotonic Overlap Graph Measures |
|
| 课程网址: | http://videolectures.net/mlg08_van_dyck_mmp/ |
| 主讲教师: | Dries Van Dyck |
| 开课单位: | 林堡跨国大学 |
| 开课时间: | 2008-08-25 |
| 课程语种: | 英语 |
| 中文简介: |  |
| 课程简介: | The main contributions of this paper are: (1) We extend the anti-monotonicity results of Vanetik, Gudes and Shimony to all 24 combinations of iso-, homo-, or homeomorphism, on labeled or unlabeled, directed or undirected graphs, with edge- or vertex-overlap. (2) We show that (under reasonable assumptions) the maximum independent set measure (MIS) of Vanetik, Gudes and Shimony (2006) is the smallest anti-monotonic measure in the class of overlap-graph based frequency measures. We also introduce the new minimum clique partition measure (MCP) which represents the largest possible one. (3) In general, both theMIS and theMCP measure are NP-hard in the size of the overlap graph. We introduce the polynomial time computable Lovasz measure, which is is sandwiched between the former two, and show that is anti-monotonic. |
| 关 键 词: | 反单调性结果; 顶点重叠; 最小集团划分措施 |
| 课程来源: | 视频讲座网 |
| 最后编审: | 2019-07-02：cjy |
| 阅读次数: | 66 |