学科分类
/ 1
1 个结果
  • 简介:GivenacompletegraphwithvertexsetXandsubsetsX1,X2,...,Xn,theproblemoffindingasubgraphGwithminimumnumberofedgessuchthatforeveryi=1,2,...,n,GcontainsaspanningtreeonXi,arisesinthedesignofvaccumsystems.Ingeneral,thisproblemisNP-completeanditisprovedthatforn=2and3thisproblemispolynomial-timesolvable.Inthispaper,weprovethatforn=4,theproblemisalsopolynomial-tlmesolvableandgiveamethodtoconstructthecorrespondinggraph.

  • 标签: 最小可行图 完全图 生成树 多项式时间可解性