计算机科学 ›› 2017, Vol. 44 ›› Issue (Z6): 129-132.doi: 10.11896/j.issn.1002-137X.2017.6A.029
张修军,吴璞,杨洪,邵泽辉
ZHANG Xiu-jun, WU Pu, YANG Hong and SHAO Ze-hui
摘要： 一个无向图G＝(V,E)的顶点子集DV是控制集,当且仅当任意一个顶点v∈V－D至少与一个顶点u∈D相邻。图G中的顶点数最少的控制集称为最小控制集,带权控制集问题是求解给定的顶点带权的无向图G的权最小的控制集。结合强弦图的性质,给出基于局部比值法的线性时间算法来求解强弦图带非负权的控制集问题,同时给出了算法复杂度的证明。
| [1] ROSE D J,TARJAN R E.Algorithmic Aspects of Vertex Elimination on Directed Graphs[J].Siam Journal on Computing,1975,34(1):245-254. [2] FARBER M.Characterizations of strongly chordal graphs[J].Discrete Mathematics,1983,43(2/3):173-189. [3] UEHARA R.Linear Time Algorithms on Chordal Bipartite and Strongly Chordal Graphs[M]∥Automata,Languages and Programming.Springer Berlin Heidelberg,2002:993-1004. [4] FARBER M.Applications of LP duality to problems involving independence and domination[D].Rutgers University,1982. [5] BOOTH K S,JOHNSON J H.Dominating sets in chordalgraphs[J].SIAM Journal on Computing,1982,11(1):191-199. [6] FARBER M.Independent domination in chordal graphs[J].Ope-rations Research Letters,1982,1(4):134-138. [7] BROIN M W,LOWE T J.A dynamic programming algorithm for covering problems with (greedy) totally balanced constraint matrices[J].SIAM Journal on Algebraic Discrete Methods,1986,7(3):348-357. [8] CHANG G J.Labeling algorithms for domination problems insun-free chordal graphs[J].Discrete Applied Mathematics,1988,22(1):21-34. [9] CHANG G J,NEMHAUSER G L.The k-domination and k-stability problems on sun-free chordal graphs[J].SIAM Journal on Algebraic Discrete Methods,1984,5(3):332-345. [10] CHANG G J,NEMHAUSER G L.Covering,packing and genera-lized perfection[J].SIAM Journal on Algebraic Discrete Me-thods,1985,6(1):109-132. [11] Farber M.Domination,independent domination,and duality in strongly chordal graphs[J].Discrete Applied Mathematics,1984,7(2):115-130. [12] HOFFMAN A J,KOLEN A W J,Sakarovitch M.Totally-ba-lanced and greedy matrices[J].SIAM Journal on Algebraic Discrete Methods,1985,6(4):721-730. [13] KRATSCH D.Finding dominating cliques efficiently,in strongly chordal graphs and undirected path graphs[J].Discrete Mathematics,1990,86(1-3):225-238. [14] WIMER T V.Linear algorithms for the dominating cycle problems in series-parallel graphs,2-trees and Halin graphs[J].Congressus Numerantium,1987,56. [15] GAREY M R,GRAHAM R L,ULLMAN J D.Worst-CaseAnalysis of Memory Allocation Algorithms[C]∥ACM Symposium on Theory of Computing.Denver,Colorado,USA,1972:93-94. [16] GAREY M R,JOHNSON D S.Computers and Intractability:A Guide to the Theory of NP-Completeness[M].W.H.Freeman and Company Ltd,1979. [17] ROSENKRANTZ D J,STEARNS R E,LEWIS P M.An analysis of several heuristics for thetraveling salesman problem[J].Siam Journal on Computing,1977,6(3):563-581. [18] BAR-YEHUDA R,EVEN S.A linear-time approximation algorithm for the weighted vertex cover problem[J].Journal of Algorithms,1981,2(2):198-203. [19] 堵丁柱.近似算法的设计与分析[M].北京:高等教育出版社,2011. |
| No related articles found! |
|
||
首页