National Taiwan Ocean University Institutional Repository:Item 987654321/40457
English  |  正體中文  |  简体中文  |  Items with full text/Total items : 27287/39131
Visitors : 2442256      Online Users : 31
RC Version 4.0 © Powered By DSPACE, MIT. Enhanced by NTU Library IR team.
Scope Adv. Search

Please use this identifier to cite or link to this item:

Title: Linear-Time Algorithms for the Paired-Domination Problem in Interval Graphs and Circular-Arc Graph
Authors: Ching-Chi Lin;Hai-Lun Tu
Contributors: 國立臺灣海洋大學:電機工程學系
Date: 2014
Issue Date: 2017-01-19T03:04:49Z
Publisher: Data Structures and Algorithms
Abstract: 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.
Appears in Collections:[Department of Computer Science and Engineering] Periodical Articles

Files in This Item:

File Description SizeFormat

All items in NTOUR are protected by copyright, with all rights reserved.


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