Exact and Parameterized Algorithms for Edge Dominating Set in 3-Degree Graphs

DOI10.1007/978-3-642-17461-2_31MaRDI QIDQ3066473zbMATH OpenOpenAlexFDO

Authors Mingyu Xiao

Publication date 10 January 2011

Published in Combinatorial Optimization and Applications (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-17461-2_31

zbMATH Keywords

exact algorithmcubic graphparameterized algorithmedge dominating set

Mathematics Subject Classification ID

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

Recommendations

• Parameterized edge dominating set in graphs with degree bounded by 3
• edge dominating set: Efficient Enumeration-Based Exact Algorithms
• A refined exact algorithm for edge dominating set
• A refined exact algorithm for edge dominating set
• Parameterized edge dominating set in cubic graphs (extended abstract)
• On matchings and \(b\)-edge dominating sets: a 2-approximation algorithm for the 3-edge dominating set problem
• New parameterized algorithms for the edge dominating set problem
• New Parameterized Algorithms for the Edge Dominating Set Problem
• Exact algorithms for edge domination
• Exact Algorithms for Edge Domination

Cited in

(12)

• New results on polynomial inapproximability and fixed parameter approximability of \textsc{Edge Dominating Set}
• Parameterized complexity of three edge contraction problems with degree constraints
• New parameterized algorithms for the edge dominating set problem
• Extension of some edge graph problems: standard and parameterized complexity
• SOFSEM 2006: Theory and Practice of Computer Science
• A multivariate framework for weighted FPT algorithms
• Parameterized edge dominating set in graphs with degree bounded by 3
• An improved algorithm for parameterized edge dominating set problem
• An improved algorithm for parameterized edge dominating set problem
• On kernelization for edge dominating set under structural parameters
• Parameterized edge dominating set in cubic graphs (extended abstract)
• On the algorithmic complexity of edge total domination

This page was built for publication: Exact and Parameterized Algorithms for Edge Dominating Set in 3-Degree Graphs

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