Inclusion/Exclusion Meets Measure and Conquer

DOI10.1007/978-3-642-04128-0_50MaRDI QIDQ3639274zbMATH OpenOpenAlexFDO

Authors Johan M. M. Van Rooij, Jesper Nederlof, Thomas C. van Dijk

Publication date 29 October 2009

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-04128-0_50

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Graph algorithms (graph-theoretic aspects) (05C85) Nonnumerical algorithms (68W05) Analysis of algorithms (68W40)

Recommendations

• Inclusion/exclusion meets measure and conquer
• Polynomial space algorithms for counting dominating sets and the domatic number
• Counting Minimum Weighted Dominating Sets
• Inclusion/Exclusion Branching for Partial Dominating Set and Set Splitting
• Algorithms and Computation

Cited in

(28)

• Exact and superpolynomial approximation algorithms for the \textsc{densest \textit{K}-subgraph} problem
• Parameterized measure \& conquer for problems with no small kernels
• Capacitated domination faster than O(2ⁿ)
• Exact algorithms for edge domination
• A note on the independence number, domination number and related parameters of random binary search trees and random recursive trees
• Inclusion/exclusion meets measure and conquer
• Space saving by dynamic algebraization based on tree-depth
• On independent sets and bicliques in graphs
• An exact exponential time algorithm for \textsc{Power} \textsc{Dominating} \textsc{Set}
• Computing the differential of a graph: hardness, approximability and exact algorithms
• A faster algorithm for dominating set analyzed by the potential method
• Solving Capacitated Dominating Set by Using Covering by Subsets and Maximum Matching
• Inclusion/Exclusion Branching for Partial Dominating Set and Set Splitting
• Separate, measure and conquer: faster polynomial-space algorithms for Max 2-CSP and counting dominating sets
• Polynomial space algorithms for counting dominating sets and the domatic number
• Counting Minimum Weighted Dominating Sets
• Exact algorithms for dominating set
• A strengthened analysis of an algorithm for dominating set in planar graphs
• Bicolored independent sets and bicliques
• Solving the 2-disjoint connected subgraphs problem faster than \(2^n\)
• Exact algorithms for minimum weighted dominating induced matching
• Scheduling partially ordered jobs faster than \(2^n\)
• Simplifying Inclusion–Exclusion Formulas
• Breaking the \(2^{n}\)-barrier for irredundance: two lines of attack
• An exact algorithm for connected red-blue dominating set
• On partitioning a graph into two connected subgraphs
• Limiting the search in brute force method for subsets detection
• The PACE 2025 parameterized algorithms and computational experiments challenge: dominating set and hitting set

This page was built for publication: Inclusion/Exclusion Meets Measure and Conquer

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