# Weighted domination of cactus graphs

**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}