期刊文献+
任意字段
题名或关键词
题名
关键词
文摘
作者
第一作者
机构
刊名
分类号
参考文献
作者简介
基金资助
栏目信息

直线簇上区间图的最小独立控制集 被引量：2

Minimum Independent Dominating Sets of Intervals on Lines
下载PDF
导出
摘要 本文研究了在三种情况下直线上的区间图的最小独立控制集的计算问题:1．相交于一点的直线簇,2．除一条直线外,其余的直线都平行的直线簇,3．一条直线和直线上t个赋权的点,使得其最小独立控制集所覆盖的点的权和最大．本文给出了这三个问题的多项式时间算法,问题1可以在O(n)时间内求解,借助动态规划方法问题2和问题 3分别可以在O(n log n),O(n+t)时间内求解． We study the problem of computing minimum independent dominating sets of n intervals on lines in three cases： （1） the lines intersect at a single point, （2） all lines except one are parallel, and （3） one line with t weighted points on it and the minimum independedt dominating set must maximize the sum of the weights of the points covered. we propose polynomial-time algorithms for these problems, the first problem has an O（n）-time solution, while the second and the third problems are solved by dynamic programming algorithms, requiring O（n log n） and （n ＋ t）-time, respectively.
作者 皮军德 康丽英 许光俊
机构地区 河南工业大学理学院 上海大学数学系
出处 《运筹学学报》 CSCD 北大核心 2006年第1期107-115,共9页 Operations Research Transactions
基金 国家自然科学基金资助课题(10101010) 上海市重点学科建设资助项目和上海市教委青年科学基金资助项目(01QN6262).
关键词 运筹学 区间图 独立控制集 算法 Operations research, interval graphs, independent dominating set, algorithms
分类号 O157.5 [理学—基础数学]
  • 相关文献

参考文献10

  • 1A.Bertossi,A.Gori.Total domination and irredundance in weighted interval graphs.SIAM J.Discrete Math.,1988,3:317～327.
  • 2B.Bollobás.Modern Graph Theory[M].New York:Spring-Verlag,2001.
  • 3K.Booth,J.Johnson.Dominating sets in chordal graphs.SIAM J.Comput.,1982,11:191～199.
  • 4K.Booth,G.Leuker.Testing for consecutive ones property,interval graph,and graph planarity using PQ-tree algorithms.J.Comput.System Sci.1976,13:335～379.
  • 5A.Brandtstaedt.The computational complexity of feedback vertex set,hamiltonian circuit,dominating set,steinertree,and bandwidth on special perfect graphs.J.Inform.Process.Cybern.,1987,23:471～474.
  • 6M.S.Chang.Efficient algorithms for the domination problems on interval and circular-arc graphs,SIAM J.Comput.,1998,6:1671～1694.
  • 7S.W.Cheng,M.Kaminski,S.Zads.Minimum dominating sets of intervals on lines.Algorithmica,1998,20:294～308.
  • 8M.C.Golumbic.Algorithmic Graph Theory and Perfect Graphs,Academic Press,New York,1980.
  • 9E.McCreight.Priority search trees.SIAM J.Comput.,1985,14:257～276.
  • 10G.Ramalingam,P.Rangan.A unified approach to domination problems on interval graphs.Inform.Process.Lett.,1988,27:271～274.

同被引文献13

  • 1徐新萍.独立集的度和与图的哈密尔顿性[J].运筹学学报,2006,10(3):109-113. 被引量：1
  • 2D.B. West. Introduction to Graph Theory, Second Edition[M]. Englewood Cliffs, N J: Prentice Hall, 2001.
  • 3S.G. Guo. On the spectral radius of unicyclic graphs with n vertices and edge independence number q[J]. Ars Combinatoria, 2007, 83: 279-287.
  • 4Sandi Klavzar. Some new bounds and exact results on the independence number of Cartesian product graphs[J]. Ars Combinatoria, 2005, 74: 173-186.
  • 5S.P. Martin, J.S. Powell,D.F. Rall. On the independence number of the Cartesian product of caterpillars[J]. Ars Combinatoria, 2001, 60: 73-84.
  • 6Ryan Pepper. An upper bound on the independence number of benzenoid systems[J]. Discrete Applied Mathematics, 2008, 156(5): 607-619.
  • 7Yusheng Li, C.C. Rousseau, Wen'an Zhang. The lower bound on independence number.[J] Science in China, Series A, 2002, 45(1): 64-69.
  • 8Mei Lu, Huiqing Liu, Feng Tian. Laplacian spectral bounds for clique and independence numbers of graphs[J]. Journal of Combinatorial Theory, Series B, 2007, 97(5): 726-732.
  • 9Eli Berger, Ran Ziv. A note on the edge cover number and independence number in hypergraphs[J]. Discrete Mathematics, 2008, 308(12): 2649-2654.
  • 10Yoshimi Egawa, Hikoe Enomoto, Dtanislav Jendrol. Independence number and vertex-disjoint cycles[J]. Discrete Mathematics, 2007, 307(11-12): 1493-1498.

引证文献2

二级引证文献2

运筹学学报
2006年 第1期

相关作者

内容加载中请稍等...

相关机构

内容加载中请稍等...

相关主题

内容加载中请稍等...

浏览历史

内容加载中请稍等...
;
使用帮助 返回顶部