National Taiwan Ocean University Institutional Repository:Item 987654321/40457
English  |  正體中文  |  简体中文  |  全文笔数/总笔数 : 27308/39152
造访人次 : 2448541      在线人数 : 117
RC Version 4.0 © Powered By DSPACE, MIT. Enhanced by NTU Library IR team.
搜寻范围 进阶搜寻

jsp.display-item.identifier=請使用永久網址來引用或連結此文件: http://ntour.ntou.edu.tw:8080/ir/handle/987654321/40457

题名: Linear-Time Algorithms for the Paired-Domination Problem in Interval Graphs and Circular-Arc Graph
作者: Ching-Chi Lin;Hai-Lun Tu
贡献者: 國立臺灣海洋大學:電機工程學系
日期: 2014
上传时间: 2017-01-19T03:04:49Z
出版者: Data Structures and Algorithms
摘要: Abstract: In a graph G, a vertex subset S⊆V(G) is said to be a dominating set of G if every vertex not in S is adjacent to a vertex in S. A dominating set S of a graph G is called a paired-dominating set if the induced subgraph G[S] contains a perfect matching. The paired-domination problem involves finding a smallest paired-dominating set of G. Given an intersection model of an interval graph G with sorted endpoints, Cheng et al. designed an O(m+n)-time algorithm for interval graphs and an O(m(m+n))-time algorithm for circular-arc graphs. In this paper, to solve the paired-domination problem in interval graphs, we propose an O(n)-time algorithm that searches for a minimum paired-dominating set of G incrementally in a greedy manner. Then, we extend the results to design an algorithm for circular-arc graphs that also runs in O(n) time.
URI: http://ntour.ntou.edu.tw:8080/ir/handle/987654321/40457
显示于类别:[資訊工程學系] 期刊論文

文件中的档案:

档案 描述 大小格式浏览次数
index.html0KbHTML45检视/开启


在NTOUR中所有的数据项都受到原著作权保护.

 


著作權政策宣告: 本網站之內容為國立臺灣海洋大學所收錄之機構典藏,無償提供學術研究與公眾教育等公益性使用,請合理使用本網站之內容,以尊重著作權人之權益。
網站維護: 海大圖資處 圖書系統組
DSpace Software Copyright © 2002-2004  MIT &  Hewlett-Packard  /   Enhanced by   NTU Library IR team Copyright ©   - 回馈