New Parameterized Algorithms for the Edge Dominating Set Problem

DOI10.1007/978-3-642-22993-0_54MaRDI QIDQ3088075zbMATH OpenOpenAlexWikidataFDO

Authors Mingyu Xiao, Ton Kloks, Sheung-Hung Poon

Publication date 17 August 2011

Published in Mathematical Foundations of Computer Science 2011 (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-22993-0_54

Mathematics Subject Classification ID

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

Recommendations

• New parameterized algorithms for the edge dominating set problem
• An improved algorithm for parameterized edge dominating set problem
• An improved algorithm for parameterized edge dominating set problem
• A refined exact algorithm for edge dominating set
• A refined exact algorithm for edge dominating set
• edge dominating set: Efficient Enumeration-Based Exact Algorithms
• New results on polynomial inapproximability and fixed parameter approximability of Edge Dominating Set
• New results on polynomial inapproximability and fixed parameter approximability of \textsc{Edge Dominating Set}
• Parameterized approximation of dominating set problems
• Linear time algorithms for generalized edge dominating set problems

Cited in

(15)

• New results on polynomial inapproximability and fixed parameter approximability of Edge Dominating Set
• Parameterized algorithms for edge biclique and related problems
• An improved algorithm for parameterized edge dominating set problem
• Kernels for edge dominating set: simpler or smaller
• Parameterized edge dominating set in cubic graphs (extended abstract)
• Exact and Parameterized Algorithms for Edge Dominating Set in 3-Degree Graphs
• Planar graph vertex partition for linear problem kernels
• Parameterized edge dominating set in graphs with degree bounded by 3
• New parameterized algorithms for the edge dominating set problem
• On the parameterized complexity of vertex cover and edge cover with connectivity constraints
• New results on directed edge dominating set
• On kernelization for edge dominating set under structural parameters
• An improved algorithm for parameterized edge dominating set problem
• A sharp upper bound for the edge dominating number of hypergraphs with minimum degree
• Parameterized complexity of generalizations of edge dominating set

This page was built for publication: New Parameterized Algorithms for the Edge Dominating Set Problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3088075)