Paper Info
Title
A Linear-Time Algorithm for the Weighted Paired-Domination Problem on Block Graphs.
Abstract
In a graph $G = (V,E)$, a vertex subset $Ssubseteq 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 $G$ is called a paired-dominating set of $G$ if the induced subgraph $G[S]$ contains a perfect matching. In this paper, we propose an $O(n+m)$-time algorithm for the weighted paired-domination problem on block graphs using dynamic programming, which strengthens the results in [Theoret. Comput. Sci., 410(47--49):5063--5071, 2009] and [J. Comb. Optim., 19(4):457--470, 2010]. Moreover, the algorithm can be completed in $O(n)$ time if the block-cut-vertex structure of $G$ is given.
Year
Venue
Field
2016
arXiv: Data Structures and Algorithms
Discrete mathematics,Graph,Dynamic programming,Dominating set,Combinatorics,Vertex (geometry),Algorithm,Induced subgraph,Matching (graph theory),Time complexity,Mathematics
DocType
Volume
Citations 
Journal
abs/1605.00372
0
PageRank 
References 
Authors
0.34
11
2
Name
Order
Citations
PageRank
Ching-Chi Lin117416.65
Cheng-Yu Hsieh212.05