Details

Autor(en) / Beteiligte

• Vietz, Duygu
• Wanke, Egon

Titel

The Fault-Tolerant Metric Dimension of Cographs

Ist Teil von

• Fundamentals of Computation Theory, p.350-364

Ort / Verlag

Cham: Springer International Publishing

Link zum Volltext

Quelle

Alma/SFX Local Collection

Beschreibungen/Notizen

• 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}$$U \subseteq V$$\end{document} of an 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} is a resolving set for G if for every two distinct vertices \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$u,v \in V$$\end{document} there is a vertex \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$w \in U$$\end{document} such that the distance between u and w and the distance between v and w are different. A resolving set U is fault-tolerant if for every vertex \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$u\in U$$\end{document} set \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$U\setminus \{u\}$$\end{document} is still a resolving set. The (fault-tolerant) metric dimension of G is the size of a smallest (fault-tolerant) resolving set for G. The weighted (fault-tolerant) metric dimension for a given cost function \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$c: V \longrightarrow \mathbb {R}_+$$\end{document} is the minimum weight of all (fault-tolerant) resolving sets. Deciding whether a given graph G has (fault-tolerant) metric dimension at most k for some integer k is known to be NP-complete. The weighted fault-tolerant metric dimension problem has not been studied extensively so far. In this paper we show that the weighted fault-tolerant metric dimension problem can be solved in linear time on cographs.