## Abstract

In a graph, an edge is said to dominate itself and its adjacent edges. Given an undirected and edge-weighted graph G = (V, E) and an integer k, Max Edge Domination problem (MaxED) is to find a subset K ⊆ E with cardinality at most k such that total weight of edges dominated by K is maximized. MaxED is NP-hard due to the NP-hardness of the minimum edge dominating set problem. In this paper, we present fixed-parameter algorithms for MaxED with respect to treewidth ω. We first present an O(3^{ω}· k·n· (k+ω))-time algorithm. This algorithm enables us to design a subexponential fixed-parameter algorithm of MaxED for apex-minor-free graphs, which is a graph class that includes planar graphs.

Original language | English |
---|---|

Pages (from-to) | 31-40 |

Number of pages | 10 |

Journal | CEUR Workshop Proceedings |

Volume | 1326 |

Publication status | Published - 2015 |

Event | 41st International Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM 2015 - Pec pod Snezkou, Czech Republic Duration: Jan 24 2015 → Jan 29 2015 |

## All Science Journal Classification (ASJC) codes

- General Computer Science