Name
Abstract | ||
|---|---|---|
A subset L subset of V of a graph G = (V, E) is called a connected liar's dominating set of G if (i) for all v. V, |NG[v] n L| >= 2, ( ii) for every pair u, v is an element of V of distinct vertices, |(N-G[u]. N-G[v]) boolean AND L| >= 3, and ( iii) the induced subgraph of G on L is connected. In this paper, we initiate the algorithmic study of minimum connected liar's domination problem by showing that the corresponding decision version of the problem is NP-complete for general graph. Next we study this problem in subclasses of chordal graphs where we strengthen the NP-completeness of this problem for undirected path graph and prove that this problem is linearly solvable for block graphs. Finally, we propose an approximation algorithm for minimum connected liar's domination problem and investigate its hardness of approximation in general graphs. |
Year | DOI | Venue |
|---|---|---|
2013 | 10.1142/S1793830913500249 | DISCRETE MATHEMATICS ALGORITHMS AND APPLICATIONS |
Keywords | Field | DocType |
Domination, liar's domination, chordal graph, graph algorithm, NP-completeness, approximation algorithm, APX-completeness | Block graph,Discrete mathematics,Dominating set,Modular decomposition,Combinatorics,Line graph,Chordal graph,Induced subgraph,Distance-hereditary graph,Pathwidth,Mathematics | Journal |
Volume | Issue | ISSN |
5 | 4 | 1793-8309 |
Citations | PageRank | References |
1 | 0.37 | 7 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| B. S. Panda | 1 | 99 | 21.18 |
| S. Paul | 2 | 13 | 4.56 |