An improved algorithm for parameterized edge dominating set problem

DOI10.7155/JGAA.00383MaRDI QIDQ2790152zbMATH OpenOpenAlexFDO

Authors Ken Iwaide, Hiroshi Nagamochi

Publication date 3 March 2016

Published in Journal of Graph Algorithms and Applications (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.7155/jgaa.00383

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Recommendations

• An improved algorithm for parameterized edge dominating set problem
• New parameterized algorithms for the edge dominating set problem
• New Parameterized Algorithms for the Edge Dominating Set Problem
• Exact and Parameterized Algorithms for Edge Dominating Set in 3-Degree Graphs
• Parameterized edge dominating set in graphs with degree bounded by 3

Cited in

(20)

• A refined exact algorithm for edge dominating set
• edge dominating set: Efficient Enumeration-Based Exact Algorithms
• An FPT-algorithm for modifying a graph of bounded treewidth to decrease the size of its dominating set using minimum modification
• A sharp upper bound for the edge dominating number of hypergraphs with minimum degree
• An Efficient Fixed-Parameter Enumeration Algorithm for Weighted Edge Dominating Set
• Parameterized edge dominating set in cubic graphs (extended abstract)
• New results on polynomial inapproximability and fixed parameter approximability of \textsc{Edge Dominating Set}
• On kernelization for edge dominating set under structural parameters
• New Parameterized Algorithms for the Edge Dominating Set Problem
• Linear time algorithms for generalized edge dominating set problems
• Improved complexity for power edge set problem
• In)approximability of Maximum Minimal FVS
• New parameterized algorithms for the edge dominating set problem
• Minimum stable cut and treewidth
• A refined exact algorithm for edge dominating set
• (In)approximability of maximum minimal FVS
• An improved algorithm for parameterized edge dominating set problem
• Parameterized edge dominating set in graphs with degree bounded by 3
• New results on directed edge dominating set
• Kernels for edge dominating set: simpler or smaller

This page was built for publication: An improved algorithm for parameterized edge dominating set problem

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