An Efficient Fixed-Parameter Enumeration Algorithm for Weighted Edge Dominating Set

DOI10.1007/978-3-642-02270-8_25MaRDI QIDQ5321717zbMATH OpenOpenAlexFDO

Authors Jianxin Wang, Beiwei Chen, Qilong Feng, Jianer Chen

Publication date 14 July 2009

Published in Frontiers in Algorithmics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-02270-8_25

zbMATH Keywords

edge dominating setminimal vertex covermatching propertyenumerate-and-expand techniquefixed-parameter enumeration algorithmweighted edge 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

• edge dominating set: Efficient Enumeration-Based Exact Algorithms
• An improved algorithm for parameterized edge dominating set problem
• Exact algorithms for edge domination
• An improved algorithm for parameterized edge dominating set problem
• New parameterized algorithms for the edge dominating set problem

Cites work

• scientific article; zbMATH DE number 610968 (Why is no real title available?)
• scientific article; zbMATH DE number 1786463 (Why is no real title available?)
• scientific article; zbMATH DE number 2119674 (Why is no real title available?)
• Algorithms for finding k-best perfect matchings
• Branching and Treewidth Based Exact Algorithms
• Efficient exact algorithms through enumerating maximal independent sets and other techniques
• Exact Algorithms for Edge Domination
• On the Effective Enumerability of NP Problems
• On two techniques of combining branching and treewidth
• Parameterized and Exact Computation
• Research in Computational Molecular Biology
• edge dominating set: Efficient Enumeration-Based Exact Algorithms

Cited in

(4)

• edge dominating set: Efficient Enumeration-Based Exact Algorithms
• Parameterized edge dominating set in cubic graphs (extended abstract)
• On kernelization for edge dominating set under structural parameters
• Extension of some edge graph problems: standard, parameterized and approximation complexity

This page was built for publication: An Efficient Fixed-Parameter Enumeration Algorithm for Weighted Edge Dominating Set

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