An Optimal Algorithm to Find a Maximum Weight 2-Coloured Set on Cactus Graphs

Abstract

A cactus graph is a connected graph in which every block is either an edge or a cycle. An )(nO time, optimal algorithm is presented here to find a maximum weight 2-coloured set on cactus graphs in where n is the total number of vertices of the graph. The cactus graph has many applications in real life problems, specially in radio communication system.