最小带宽问题

我很有趣的是NP-complete“最小带宽”问题，用于查找图的最小带宽。对于那些不熟悉的人，这里有一个关于它的链接...... http://en.wikipedia.org/wiki/Graph_bandwidth 我已经实现了Cuthill-McKee算法，这非常成功地让我对带宽减少的顶点进行了排列;但是，我正在寻找最小带宽，而不仅仅是减少的带宽。如果您有任何遇到此问题的经验，那么哪些算法提供的解决方案是最小的而不仅仅是减少了？我不需要任何算法的实际实现，我只是想要研究什么算法来产生实际的最小带宽。

已邀请:

3 个回复

脾萌

这是一个有趣的问题，但是当我读到Wiki（你的链接）时：都是未加权和加权的版本是特殊情况二次瓶颈分配问题。带宽问题是 NP难，即使是一些特殊的例。[4]关于存在它是有效的近似算法众所周知，带宽是NP难的在任何常数内近似，这甚至在输入时都成立图表仅限于卡特彼勒树木（Dubey，Feige＆amp; Unger 2010）。上另一方面，一些多项式可解的特例众所周知。所以维基说NP-Hard用任何常数逼近它（所以没有针对这个问题的PTAS）你的机会就是使用启发式算法，确保强力算法有效，（编号节点的数字在1..n之间随机出现）启动后，使用蛮力）但你应该花1000年时间为卡特彼勒解决它。您应该搜索启发式算法，而不是近似和精确算法。