【摘 要】
：
给定边具有正权的无向图,并指定若干个称为终端的顶点,最小最大多路割问题是要得到所有顶点的一个聚类,要求每个子类恰好包含一个终端,并使得所有子类的最大费用最小。子类的
【机 构】
：
山东工商学院计算机科学与技术学院,山东大学计算机科学与技术学院,山东工商学院外国语学院
【基金项目】
：
国家自然科学基金（60970105）, 山东省信息产业发展专项资金项目（2008X00039）, 山东省软科学研究计划（2010RKE20029）资助
论文部分内容阅读
给定边具有正权的无向图,并指定若干个称为终端的顶点,最小最大多路割问题是要得到所有顶点的一个聚类,要求每个子类恰好包含一个终端,并使得所有子类的最大费用最小。子类的费用定义为该子类边界上所有边的权之和。最小最大多路割问题源于对等网络中的数据放置,是传统多路割问题的一个变形。当给定无向图是树图时,这一问题已经是强NP难解的。对于链图和环图,给出了线性时间的精确算法,该算法同时也使得所有子类的总费用最小。对于树图和限制树宽图,给出了（2-21k2）-近似算法,k表示终端的数目。
其他文献
目的探讨乳腺透明细胞癌(glycogen-rich clear cell carcinoma of breast,GRCCC)的临床病理特征和诊断要点。方法报道1 例GRCCC 的临床病理、免疫组织化学结果及预后,并复习
目的通过检测卡介苗对阿尔茨海默症（AD）模型小鼠学习记忆等行为和脑内Aβ的影响,探索卡介苗治疗阿尔茨海默症的可能性。方法 12周龄的C57BL/6小鼠随机分成3组,每组8只,分别为生
为了同时兼顾改善不同往返时延（RTT）和多拥塞链路所引发的不公平性问题,在实际网络环境测量结果的基础上,提出了利用数据包所经过的路由器跳数来增强公平性的思路,并构造了一个
P2P环境提供了便捷的资源共享和直接通信,但也使病毒等获得了更为方便的传播和感染渠道。提出一种基于免疫协作的混合式对等网络病毒检测模型,利用对等节点间的协作实现记忆
提出了一种基于仿射传播聚类(Affinity Propagation Clustering,AP Clustering)和仿生模式识别理论(Biomi-metic Pattern Recognition,BPR)的识别方法。该方法通过AP聚类选择代表训练样本,依据仿生模式识别理论构建并划分样本空间,通过计算待识样本到各特征子空间的相对距离,根据其所处空间进行分类识别。在因空间重叠造成拒识的情况下,
多平台怎么进行协同,是多平台防空体系建设过程中面临的最为关键的问题之一。在介绍协同机制在多平台防空体系中的重要作用的基础上,归纳和描述了多平台防空体系中的各种不同
针对目前网络科技文献共享平台上汇聚的海量的科技文献,提出了一种新的基于智能Agent的科技文献快速协作推送模型,通过引入由智能Agent技术构建的用户Agent、数据传递Agent、