Weighted domination of cactus graphs

Janez Žerovnik
University of Ljubljana

Tina Novak
University of Ljubljana

PDF

Minisymposium: GENERAL SESSION TALKS

Content: Cactus is a graph in which every edge is on at most one cycle. Or, equivalently, each pair of cycles can meet in at most one vertex. A linear algorithm for weighted domination number of (vertex-weighted) cactus graphs is given. Although algorithms for the domination problem on trees and cacti are known for a long time [1,2], there seems to be no work that studies the weighted domination problem on cactus graphs. However, as cacti are graphs with tree-width $k=2$, the general algorithm of [3] can be used that solves the weighted domination problem in ${\cal O}(3^{2k+1}n) = {\cal O}(3^{5}n)$ steps. Our algorithm needs at most $16n$ additions and $10n$ min operations and thus substantially improves the constant factor. \vspace{5mm} \noindent{\bf References:} \begin{itemize} \item[{[1]}] E.J. Cockayne, S.E. Goodman, and S.T. Hedetniemi, A linear algorithm for the domination number of a tree, {\it Information Processing Letters} {\bf 4} (1975) 41--44. \item[{[2]}] S.T. Hedetniemi, R. Laskar, and J. Pfaff, A linear algorithm for finding a minimum dominating set in a cactus, {\it Discrete Applied Mathematics} {\bf 13} (1986) 287--292. \item[{[3]}] J.A. Telle and A. Proskurowski, Practical Algorithms on Partial $k$-Trees with an Application to Domination-like Problems, {\it Algorithms and Data Structures, Lecture Notes in Computer Science} {\bf 709} (1993) 610--621. \end{itemize}

Back to all abstracts