首页 | 本学科首页   官方微博 | 高级检索  
     检索      


Approximating k-cuts using network strength as a Lagrangean relaxation
Authors:R Ravi  Amitabh Sinha
Institution:1. Tepper School of Business, Carnegie Mellon University, Pittsburgh, PA 15213, USA;2. Ross School of Business, University of Michigan, Ann Arbor, MI 48109, USA
Abstract:Given an undirected, edge-weighted connected graph, the k-cut problem is to partition the vertex set into k non-empty connected components so as to minimize the total weight of edges whose end points are in different components.
Keywords:Combinatorial optimization  Graph theory  Approximation algorithm  Lagrangean relaxation
本文献已被 ScienceDirect 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号