山东大学学报（理学版）
山東大學學報（理學版）
산동대학학보（이학판）
JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE)
2007年
8期
67-69
,共3页
算法%多端割%广义树网络%动态规划
算法%多耑割%廣義樹網絡%動態規劃
산법%다단할%엄의수망락%동태규화
给定一个边赋权图和k个顶点(称为终端)的集合,多端割问题是要找到一个最小权的边集,该边集使得每一个终端与其他所有的终端分离.对于一般图来说,当k为不小于3的常数时,这一问题是NP-难解的.对于广义树网络给出了这一问题的一个多项式时间精确算法.
給定一箇邊賦權圖和k箇頂點(稱為終耑)的集閤,多耑割問題是要找到一箇最小權的邊集,該邊集使得每一箇終耑與其他所有的終耑分離.對于一般圖來說,噹k為不小于3的常數時,這一問題是NP-難解的.對于廣義樹網絡給齣瞭這一問題的一箇多項式時間精確算法.
급정일개변부권도화k개정점(칭위종단)적집합,다단할문제시요조도일개최소권적변집,해변집사득매일개종단여기타소유적종단분리.대우일반도래설,당k위불소우3적상수시,저일문제시NP-난해적.대우엄의수망락급출료저일문제적일개다항식시간정학산법.
