Linear-Time Algorithm for the Paired-Domination Problem in Convex Bipartite Graphs

作     者：Hung, Ruo-Wei 

作者机构：Chaoyang Univ Technol Dept Comp Sci & Informat Engn Taichung 41349 Taiwan 

出 版 物：《THEORY OF COMPUTING SYSTEMS》 (计算系统理论)

年 卷 期：2012年第50卷第4期

页      面：721-738页

核心收录：

学科分类：07[理学] 0701[理学-数学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 070101[理学-基础数学] 

主　　题：Graph algorithms Linear-time algorithms Paired-domination Total domination Convex bipartite graphs 

摘      要：A bipartite graph G=(U,W,E) with vertex set V=Ua(a)W is convex if there exists an ordering of the vertices of W such that for each uaU, the neighbors of u are consecutive in W. A compact representation of a convex bipartite graph for specifying such an ordering can be computed in O(|V|+|E|) time. The paired-domination problem on bipartite graphs has been shown to be NP-complete. The complexity of the paired-domination problem on convex bipartite graphs has remained unknown. In this paper, we present an O(|V|) time algorithm to solve the paired-domination problem on convex bipartite graphs given a compact representation. As a byproduct, we show that our algorithm can be directly applied to solve the total domination problem on convex bipartite graphs in the same time bound.