Design by measure and conquer. A faster exact algorithm for dominating set

DOI10.4230/LIPICS.STACS.2008.1329MaRDI QIDQ4910758zbMATH OpenFDO

Authors Johan M. M. Van Rooij, Hans L. Bodlaender

Publication date 19 March 2013

Full work available at URL http://subs.emis.de/LIPIcs/frontdoor_ed28.html

zbMATH Keywords

branch and reducecomputer aided algorithm designdominating setexact algorithmsexponential time algorithmsmeasure and conquer

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Computer science aspects of computer-aided design (68U07)

Recommendations

• Exact algorithms for dominating set
• A measure \& conquer approach for the analysis of exact algorithms
• Automata, Languages and Programming
• A faster algorithm for dominating set analyzed by the potential method
• A refined exact algorithm for edge dominating set

Cited in

(22)

• Efficient approximation of Min Set Cover by moderately exponential algorithms
• Parameterized measure \& conquer for problems with no small kernels
• Solving the minimum M-dominating set problem by a continuous optimization approach based on DC programming and DCA
• Exact algorithms for edge domination
• Fast algorithms for max independent set
• On independent sets and bicliques in graphs
• An exact exponential time algorithm for \textsc{Power} \textsc{Dominating} \textsc{Set}
• Sharp separation and applications to exact and parameterized algorithms
• A faster algorithm for dominating set analyzed by the potential method
• Turbo-charging dominating set with an FPT subroutine: further improvements and experimental analysis
• Enumerate and measure: improving parameter budget management
• Inclusion/Exclusion Branching for Partial Dominating Set and Set Splitting
• Efficient Approximation of Combinatorial Problems by Moderately Exponential Algorithms
• A measure \& conquer approach for the analysis of exact algorithms
• Exact Algorithms for Edge Domination
• Exact algorithms for dominating set
• A strengthened analysis of an algorithm for dominating set in planar graphs
• On Independent Sets and Bicliques in Graphs
• Automata, Languages and Programming
• An exact algorithm for connected red-blue dominating set
• Branch and recharge: exact algorithms for generalized domination
• Finding a dominating set on bipartite graphs

This page was built for publication: Design by measure and conquer. A faster exact algorithm for dominating set

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