众所周知，在图中寻找极大团是NP-完全问题.但我不知道是否有可能在多项式时间内找到图中的子极大团。也就是说，考虑到我们不知道是否存在P=NP，是否有一个多项式算法会给出一个团的大小是，至少是，最大团大小减去1？我猜答案是“不”，因为我知道没有多项式时间算法可以给出一个大小正好是的最大团大小减去1的团，否则我就会知道这个算法在多项式时间内的最大团的大小，如果P!=NP的话，这是不可能的。但我不知道如何证明，当我们期望算法</em
浏览 12提问于2022-04-30得票数 0
1回答
我试图理解Bron的算法(带旋转)，以求无向图中的最大团。我有一些问题：
选择一个枢轴顶点有什么标准吗？该算法不对所有顶点进行旋转检查，以确定其是否形成一个团，而具有旋转的算法只检查P \ N(u)中必须包含的顶点，以形成一个最大团。这样，如果找到一个非最大团，算法就可以立即回溯，而不是在永远不会形成最大团的顶点上执行不必要的递归。我的理解正确吗？
浏览 6提问于2021-04-09得票数 3
回答已采纳
3回答
将列表划分为组的算法
、、、
什么算法(如果可能，请使用Java风格的伪代码！)确定最合适的组大小？列表包含13个名称-最大团队规模为3。输出(团队规模)：3，3，3，2，2列表包含31个名称-最大团队规模为5。输出: 5，5，5，4，4，4，4列表包含31个名称-最大团队规模为10。输出: 8，8，8，7
浏览 0提问于2012-01-12得票数 4
回答已采纳
1回答
我希望找到至少有k个节点的所有极大团(认为边是无向的)。有没有cypher查询或neo4j插件可以帮到我？有没有其他方法来解决这个问题呢？
浏览 3提问于2021-06-08得票数 0
2回答
是否有一种已知的算法或方法可以在图中找到所有完整的子图？我有一个无向、无权重的图，我需要找到其中每个子图中的每个节点都与子图中的其他节点相连的所有子图。
有没有现成的算法来解决这个问题呢？
浏览 4提问于2010-05-10得票数 22
回答已采纳
1回答
我有一个中等大小的图(570个节点，69127条边，密度:0.42in gexf格式)，我想枚举所有大小大于N(比方说5)的集团。可用的最有效的方法是什么？我正在寻找任何流行语言或软件包的库。
浏览 3提问于2012-04-24得票数 2
回答已采纳
d，e}最大完全二部图是：{C，D}-{c，d}我找到了一个强力算法我不知道是某种近似算法还是随机化算法。
浏览 2提问于2013-03-29得票数 6
回答已采纳
2回答
边缘团覆盖算法
、、、、
我试图编写一个算法来计算输入图(无向和无自循环)的边团覆盖数(覆盖所有边的最小团数)。我的想法是
有谁知道一个更好的方法吗?有标准的算法吗？令我惊讶的是，我找不到任何这样的算法。我知道这个问题是NP难的，所以我不期望有一个快速的解决方案。
浏览 2提问于2018-03-06得票数 3
回答已采纳
2回答
我有一个问题，我可以将其建模为在二部图中寻找最大二色(完全二部图)。我知道Bron-Kerbosch算法用于检测最大团，在我看来，应该有一种方法来表示两团问题为团问题。有没有人有一个解决方案，既可以形成一个集团问题，也可以作为直接检测双集团的有效算法？
浏览 3提问于2010-06-18得票数 5
回答已采纳
我有一个很大的图，我会找到涉及一对顶点的最大团。我认为igraph的maximal.clique函数的子集参数可以做到这一点，但是要么我用错了它，要么它做了完全不同的事情。下面是一个很小的例子，说明了这个问题：> packageVersion('igraph')> g = graph.empty(n=10,
浏览 8提问于2016-04-12得票数 0
回答已采纳
1回答
这似乎是一个简单的问题，但我被这个问题卡住了。问题是我有一个大小为X x Y的矩阵。在(i，j)处可能有一些点。然而，并非所有位置(i，j)都应该具有点(即，存在< XY点)。
浏览 0提问于2011-11-17得票数 1
回答已采纳
我使用networkx库实现了Bron-Kerbosch库的算法来找到图G中的所有最大团。为了加快我的分析速度，在非常大的图中，我想修改这个算法来从图G中只提取一个最大团。修改这个算法是最好的解决方案，还是有更有效的算法？
浏览 21提问于2021-08-01得票数 0
2回答
在完全图中寻找最大团
、、、
在一个有大约100个顶点的完美图(这个图有至少1个弦的奇数圈)中找到最大团的快速算法?？
还有比暴力更简单的方法吗，因为这是一个完美的图，应该有一个多项式时间的解。但是我找不到算法。
浏览 3提问于2010-06-11得票数 5
函数背后的算法是什么？这显然不是一个蛮力的方法，因为它的良好性能。
即使点击“源代码”链接似乎也没有显示出来。这在文档中有解释吗？
浏览 0提问于2018-05-11得票数 0
回答已采纳
2回答
给定一个无向图G= G(V，E)，如何在多项式时间内找到其中最大团的大小？有没有更有效的方法来解决这个NP完全问题？
浏览 5提问于2014-03-31得票数 1
1回答
我想找出连通图中包含某些顶点的最大团。在wiki中，它说贪婪的搜索可以找到一个最大的集团。然而，这并不能确保你找到最大的集团国际海事组织。我知道这是个愚蠢的问题，但如果有人能告诉我这个方法是否正确，我会非常感激的。
浏览 4提问于2017-06-21得票数 2
回答已采纳
扫码
添加站长 进交流群
领取专属 10元无门槛券
手把手带您无忧上云
相关资讯
热门标签
云服务器
ICP备案
对象存储
腾讯会议
云直播活动推荐
腾讯云开发者
