Geodesic
Algorithm and Hardness Results for Outer-connected Dominating Set in Graphs
Journal of Graph Algorithms and Applications, Special Issue on Selected Papers from the Eighth International Workshop on Algorithms and Computation, WALCOM 2014 , Tome 18 (2014) no. 4, pp. 493-513.

Voir la notice de l'article provenant de la source Journal of Graph Algorythms and Applications website

A set D ⊆ V of a graph G = (V,E) is called an outer-connected dominating set of G if for all v ∈ V, |NG[v]∩D| ≥ 1, and the induced subgraph of G on V\D is connected. The MINIMUM OUTER-CONNECTED DOMINATION problem is to find an outer-connected dominating set of minimum cardinality of the input graph G. Given a positive integer k and a graph G=(V,E), the OUTER-CONNECTED DOMINATION DECISION problem is to decide whether G has an outer-connected dominating set of cardinality at most k. The OUTER-CONNECTED DOMINATION DECISION problem is known to be NP-complete for bipartite graphs. In this paper, we strengthen this NP-completeness result by showing that the OUTER-CONNECTED DOMINATION DECISION problem remains NP-complete for perfect elimination bipartite graphs. On the positive side, we propose a linear-time algorithm for computing a minimum outer-connected dominating set of a chain graph, a subclass of bipartite graphs. We show that the OUTER-CONNECTED DOMINATION DECISION problem can be solved in linear-time for graphs of bounded tree-width. We propose a ∆(G)-approximation algorithm for the MINIMUM OUTER-CONNECTED DOMINATION problem, where ∆(G) is the maximum degree of G. On the negative side, we prove that the MINIMUM OUTER-CONNECTED DOMINATION problem cannot be approximated within a factor of (1−ε)ln|V| for any ε > 0, unless NP ⊆ DTIME(|V|O(loglog|V|)). We also show that the MINIMUM OUTER-CONNECTED DOMINATION problem is APX-complete for graphs with bounded degree 4 and for bipartite graphs with bounded degree 7. 
@article{JGAA_2014_18_4_a1,
     author = {B. Panda and Arti Pandey},
     title = {Algorithm and {Hardness} {Results} for {Outer-connected} {Dominating} {Set} in {Graphs}},
     journal = {Journal of Graph Algorithms and Applications},
     pages = {493--513},
     publisher = {mathdoc},
     volume = {18},
     number = {4},
     year = {2014},
     doi = {10.7155/jgaa.00334},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00334/}
}
TY  - JOUR
AU  - B. Panda
AU  - Arti Pandey
TI  - Algorithm and Hardness Results for Outer-connected Dominating Set in Graphs
JO  - Journal of Graph Algorithms and Applications
PY  - 2014
SP  - 493
EP  - 513
VL  - 18
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00334/
DO  - 10.7155/jgaa.00334
LA  - en
ID  - JGAA_2014_18_4_a1
ER  - 
%0 Journal Article
%A B. Panda
%A Arti Pandey
%T Algorithm and Hardness Results for Outer-connected Dominating Set in Graphs
%J Journal of Graph Algorithms and Applications
%D 2014
%P 493-513
%V 18
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00334/
%R 10.7155/jgaa.00334
%G en
%F JGAA_2014_18_4_a1
B. Panda; Arti Pandey. Algorithm and Hardness Results for Outer-connected Dominating Set in Graphs. Journal of Graph Algorithms and Applications, 
							Special Issue on Selected Papers from the Eighth International Workshop on Algorithms and Computation, WALCOM 2014
					, Tome 18 (2014) no. 4, pp. 493-513. doi : 10.7155/jgaa.00334. http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00334/

Cité par Sources :