本文選題：局部比值法 + 強弦圖　； 參考：《計算機科學》2017年S1期

【摘要】：一個無向圖G=(V,E)的頂點子集D■V是控制集,當且僅當任意一個頂點v∈V-D至少與一個頂點u∈D相鄰。圖G中的頂點數(shù)最少的控制集稱為最小控制集,帶權(quán)控制集問題是求解給定的頂點帶權(quán)的無向圖G的權(quán)最小的控制集。結(jié)合強弦圖的性質(zhì),給出基于局部比值法的線性時間算法來求解強弦圖帶非負權(quán)的控制集問題,同時給出了算法復雜度的證明。
[Abstract]:The vertex subset D V of an undirected graph G / V is a dominating set if and only if any vertex v 鈭，

本文編號：1770373