一个图论题# JobHunting - 待字闺中
f*e
1 楼
【 以下文字转载自 Mathematics 讨论区 】
发信人: fatalme (don't ever give it up), 信区: Mathematics
标 题: 一个图论题
发信站: BBS 未名空间站 (Sun Sep 18 00:01:11 2011, 美东)
有一个图G和映射pi，|V|=n，映射pi把G的节点映射到1...n
pi(V) ->{i:i=1..n}
然后对于每个e in E， e的两个端点， |pi(i)-pi(j)|<20
有什么polynomial方法找到G的independent set吗？
发信人: fatalme (don't ever give it up), 信区: Mathematics
标 题: 一个图论题
发信站: BBS 未名空间站 (Sun Sep 18 00:01:11 2011, 美东)
有一个图G和映射pi，|V|=n，映射pi把G的节点映射到1...n
pi(V) ->{i:i=1..n}
然后对于每个e in E， e的两个端点， |pi(i)-pi(j)|<20
有什么polynomial方法找到G的independent set吗？