linear-time algorithms for edge domination in block-cactus graphs

In a graph G = (V; E), a subset F ⊆ E is an edge dominating set if every edge e 2 E n F is adjacent to at least one edge in F. The edge domination problem is to find a minimum edge dominating set of G. This paper studies edge domination problem from an algorithmic point of view. Our final goal is to present a linear-time algorithm solving the edge domination problem in block-cactus graphs, which is a superclass of both block graphs and cacti. Our algorithm is based on the using of edge-label method and the handling of a series of configurations in block-cactus graphs, so as by-products, we also design different algorithms and procedures for these configurations, including , tree, cycle, sun, cactus, part tree, end sun and end clique, etc.