Inclusion/Exclusion Branching for Partial Dominating Set and Set Splitting

DOI10.1007/978-3-642-17493-3_20MaRDI QIDQ3058704zbMATH OpenOpenAlexFDO

Authors Jesper Nederlof, Johan M. M. Van Rooij

Publication date 7 December 2010

Published in Parameterized and Exact Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-17493-3_20

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Analysis of algorithms and problem complexity (68Q25) Analysis of algorithms (68W40)

Recommendations

• Dominating sets for split and bipartite graphs
• Set partitioning via inclusion-exclusion
• scientific article; zbMATH DE number 1202982
• scientific article; zbMATH DE number 6311742
• scientific article; zbMATH DE number 139923
• Branch and recharge: exact algorithms for generalized domination
• Branch and Recharge: Exact Algorithms for Generalized Domination
• scientific article; zbMATH DE number 749271
• Inclusion/Exclusion Meets Measure and Conquer
• Implicit branching and parameterized partial cover problems

Cites work

• A measure \& conquer approach for the analysis of exact algorithms
• Design by measure and conquer. A faster exact algorithm for dominating set
• Even faster algorithm for set splitting!
• Fast Polynomial-Space Algorithms Using Möbius Inversion: Improving on Steiner Tree and Related Problems
• Fourier meets M\"{o}bius: fast subset convolution
• Graph-Theoretic Concepts in Computer Science
• scientific article; zbMATH DE number 1953201 (Why is no real title available?)
• Implicit branching and parameterized partial cover problems (extended abstract)
• Improved parameterized set splitting algorithms: A Probabilistic approach
• Inclusion/Exclusion Meets Measure and Conquer
• Limits and Applications of Group Algebras for Parameterized Problems
• On the complexity of k-SAT
• On two techniques of combining branching and treewidth
• Parameterized and Exact Computation
• Partial vs. Complete Domination: t-Dominating Set
• Polynomial space algorithms for counting dominating sets and the domatic number
• Set partitioning via inclusion-exclusion
• Subexponential algorithms for partial cover problems
• The Travelling Salesman Problem in Bounded Degree Graphs
• Trimmed Moebius inversion and graphs of bounded degree

Cited in

(3)

• Exact and parameterized algorithms for \textsc{Max Internal Spanning Tree}
• Inclusion/Exclusion Meets Measure and Conquer
• Simplifying Inclusion–Exclusion Formulas

This page was built for publication: Inclusion/Exclusion Branching for Partial Dominating Set and Set Splitting

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