Algorithm 版 (精华区)

发信人: ssos (存在与虚无), 信区: Algorithm
标  题: 可计算性简明纲要(11)
发信站: 哈工大紫丁香 (2001年06月14日15:44:10 星期四), 站内信件

覆盖问题 任给一集合族,任给整数k,判定族内存在k个集合,它们的
并包含族内出现过的所有元素.
分划问题 任给一集合族,判定族内存在若干集合,构成对族内所有
集合的并的一个分划.
k-分划问题 任给一集合族,和一整数k,判定族内存在k个集合,构
成对族内所有集合的并的一个分划.
图的边的Blocking Set问题 任给一图,和整数k,判定存在k条边,
使得所有顶点都与其中至少一条相关.
独立集问题 任给一图,和整数k,判定有k顶点的独立集.
团问题 任给一图,和整数k,判定有k顶点的团.
图的嵌入问题 任给一图A和一图B,判定B是A的子图.
着色问题 任给一图,和整数k,判定该图可以k着色.
k-着色(k>=3) 任给一图,判定该图可以k着色.

--

   
<<社会契约论>>是一本好书,应当多读几遍
风味的肘子味道不错,我还想再吃它      

※ 来源:·哈工大紫丁香 bbs.hit.edu.cn·[FROM: 202.118.230.220]