A refined exact algorithm for edge dominating set

DOI10.1016/J.TCS.2014.07.019MaRDI QIDQ477194zbMATH OpenOpenAlexFDO

Authors Mingyu Xiao, Hiroshi Nagamochi

Publication date 2 December 2014

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

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

zbMATH Keywords

exact algorithmmeasure and conqueredge 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

• A refined exact algorithm for edge dominating set
• Exact Algorithms for Edge Domination
• Exact algorithms for edge domination
• An improved algorithm for parameterized edge dominating set problem
• edge dominating set: Efficient Enumeration-Based Exact Algorithms

Cites work

• A measure \& conquer approach for the analysis of exact algorithms
• Confining sets and avoiding bottleneck cases: a simple maximum independent set algorithm in degree-3 graphs
• Constrained weighted matchings and edge coverings in graphs
• Edge Dominating Sets in Graphs
• Efficiency in exponential time for domination-type problems
• Efficient exact algorithms through enumerating maximal independent sets and other techniques
• Enumerate and measure: improving parameter budget management
• Exact algorithms for edge domination
• New parameterized algorithms for the edge dominating set problem
• On cliques in graphs
• On generating all maximal independent sets
• On two techniques of combining branching and treewidth
• Parameterized edge dominating set in graphs with degree bounded by 3
• Quasiconvex analysis of multivariate recurrence equations for backtracking algorithms
• edge dominating set: Efficient Enumeration-Based Exact Algorithms

Cited in

(12)

• A refined exact algorithm for edge dominating set
• Exact algorithms for dominating set
• Exact algorithms for maximum induced matching
• On kernelization for edge dominating set under structural parameters
• New Parameterized Algorithms for the Edge Dominating Set Problem
• Exact and Parameterized Algorithms for Edge Dominating Set in 3-Degree Graphs
• Exact Algorithms for Edge Domination
• Branch and recharge: exact algorithms for generalized domination
• Exact algorithms for dominating induced matching based on graph partition
• Exact algorithms for edge domination
• New results on directed edge dominating set
• Edge domination number and the number of minimum edge dominating sets in pseudofractal scale-free web and Sierpiński gasket

This page was built for publication: A refined exact algorithm for edge dominating set

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