作者：杨朝霞最小阻塞超图嵌入带权圈近似算法
摘要：超图嵌入带权圈（HEWC）问题就是把超图的超边以路的形式嵌入一个带权圈，使得圈上任何带权连接边的最大阻塞最小。这个问题的一个简单形式是图嵌入带权圈（GEWC），即把普通图的边以路的形式嵌入一个带权圈。HEWC问题第一次被归结为一个整数线性规划问题，并且利用LP的放松问题和有界启发得到一个近似解。然后设计了一个非常简单有用的可以和LP近似算法得到一样好的近似解的线性时间近似算法。
注：因版权方要求，不能公开全文，如需全文，请咨询杂志社
《山东大学学报·理学版》（CN：37-1389/N）是一本有较高学术价值的大型月刊，自创刊以来，选题新奇而不失报道广度，服务大众而不失理论高度。颇受业界和广大读者的关注和好评。 《山东大学学报·理学版》为理工科综合性学术期刊。旨在反映该校自然科学领域中的最新研究成果，促进学术交流，活跃学术思想。
杂志详情
