New parameterized algorithms for the edge dominating set problem

DOI10.1016/j.tcs.2012.06.022zbMath1407.68231OpenAlexW2043913527WikidataQ62041768 ScholiaQ62041768MaRDI QIDQ392035

Mingyu Xiao, Sheung-Hung Poon, Ton Kloks

Publication date: 13 January 2014

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2012.06.022

zbMATH Keywords

graph algorithmsparameterized algorithmskernelizationedge dominating set

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (15)

On approximating (connected) 2-edge dominating set by a tree ⋮ A Multivariate Approach for Weighted FPT Algorithms ⋮ Kernelization of edge perfect code and its variants ⋮ A multivariate framework for weighted FPT algorithms ⋮ New Results on Directed Edge Dominating Set ⋮ Space limited graph algorithms on big data ⋮ Space limited linear-time graph algorithms on big data ⋮ A refined exact algorithm for edge dominating set ⋮ Maximum matching and kernelization of edge dominating set ⋮ On Approximating (Connected) 2-Edge Dominating Set by a Tree ⋮ Unnamed Item ⋮ Fast and Simple Local Algorithms for 2-Edge Dominating Sets and 3-Total Vertex Covers ⋮ Upper and lower bounds on approximating weighted mixed domination ⋮ Improved parameterized algorithms and kernels for mixed domination ⋮ New results on polynomial inapproximability and fixed parameter approximability of Edge Dominating Set

Cites Work

• Unnamed Item
• Improved approximation bounds for edge dominating set in dense graphs
• On two techniques of combining branching and treewidth
• On generating all maximal independent sets
• A 2-approximation algorithm for the minimum weight edge dominating set problem
• Efficient exact algorithms through enumerating maximal independent sets and other techniques
• A Refined Exact Algorithm for Edge Dominating Set
• Parameterized Edge Dominating Set in Cubic Graphs
• Enumerate and Measure: Improving Parameter Budget Management
• A Simple and Fast Algorithm for Maximum Independent Set in 3-Degree Graphs
• edge dominating set: Efficient Enumeration-Based Exact Algorithms
• Exact Algorithms for Edge Domination
• Edge Dominating Sets in Graphs
• On cliques in graphs

This page was built for publication: New parameterized algorithms for the edge dominating set problem