Details

Autor(en) / Beteiligte

• Panda, B. S
• Goswami, Partha P

Titel

Efficient Domination and Efficient Edge Domination: A Brief Survey

Ist Teil von

• Algorithms and Discrete Applied Mathematics, 2018, Vol.10743, p.1-14

Ort / Verlag

Switzerland: Springer International Publishing AG

Erscheinungsjahr

2018

Link zum Volltext

Quelle

Alma/SFX Local Collection

Beschreibungen/Notizen

• In a finite undirected graph \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$G=(V,E)$$\end{document}, a vertex \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$v \in V$$\end{document}dominates itself and its neighbors in G. A vertex set \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$D \subseteq V$$\end{document} is an efficient dominating set (e.d.s. for short) of G if every \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$v \in V$$\end{document} is dominated in G by exactly one vertex of D. The Efficient Domination (ED) problem, which asks for the existence of an e.d.s. in G, is known to be \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathbb {NP}$$\end{document}-complete for bipartite graphs, for (very special) chordal graphs and for line graphs but solvable in polynomial time for many subclasses. For H-free graphs, a dichotomy of the complexity of ED has been reached. An edge set \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$M \subseteq E$$\end{document} is an efficient edge dominating set (e.e.d.s. for short) of G if every \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$e \in E$$\end{document} is dominated in G by exactly one edge of M with respect to the line graph L(G). Thus, M is an e.e.d.s. in G if and only if M is an e.d.s. in L(G). An e.e.d.s. is called dominating induced matching in various papers. The Efficient Edge Domination (EED) problem, which asks for the existence of an e.e.d.s. in G, is known to be \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathbb {NP}$$\end{document}-complete even for special bipartite graphs but solvable in polynomial time for various graph classes.The problems ED and EED are based on the \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathbb {NP}$$\end{document}-complete Exact Cover problem on hypergraphs.