Name
Abstract | ||
|---|---|---|
Let G=(V,E) be a graph without isolated vertices and having at least 3 vertices. A set L@?V(G) is a liar@?s dominating set if (1) |N"G[v]@?L|=2 for all v@?V(G), and (2) |(N"G[u]@?N"G[v])@?L|=3 for every pair u,v@?V(G) of distinct vertices in G, where N"G[x]={y@?V|xy@?E}@?{x} is the closed neighborhood of x in G. Given a graph G and a positive integer k, the liar@?s domination problem is to check whether G has a liar@?s dominating set of size at most k. The liar@?s domination problem is known to be NP-complete for general graphs. In this paper, we propose a linear time algorithm for computing a minimum cardinality liar@?s dominating set in a proper interval graph. We also strengthen the NP-completeness result of liar@?s domination problem for general graphs by proving that the problem remains NP-complete even for undirected path graphs which is a super class of proper interval graphs. |
Year | DOI | Venue |
|---|---|---|
2013 | 10.1016/j.ipl.2013.07.012 | Information Processing Letters |
Keywords | Field | DocType |
NP-completeness result,undirected path graph,general graph,linear time algorithm,minimum cardinality liar,set L,domination problem,graph G,closed neighborhood,positive integer k,proper interval graph | Discrete mathematics,Combinatorics,Dominating set,Indifference graph,Vertex (geometry),Interval graph,Chordal graph,Algorithm,Independent set,Pathwidth,Mathematics,Maximal independent set | Journal |
Volume | Issue | ISSN |
113 | 19-21 | 0020-0190 |
Citations | PageRank | References |
6 | 0.55 | 7 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| B. S. Panda | 1 | 99 | 21.18 |
| S. Paul | 2 | 13 | 4.56 |