Inclusion/Exclusion Meets Measure and Conquer

DOI10.1007/978-3-642-04128-0_50zbMath1256.68158OpenAlexW2103164681MaRDI QIDQ3639274

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

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

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

Related Items (24)

A Faster Algorithm for Dominating Set Analyzed by the Potential Method ⋮ Separate, Measure and Conquer: Faster Polynomial-Space Algorithms for Max 2-CSP and Counting Dominating Sets ⋮ Space saving by dynamic algebraization based on tree-depth ⋮ Exact and superpolynomial approximation algorithms for the \textsc{densest \textit{K}-subgraph} problem ⋮ Exact algorithms for dominating set ⋮ A strengthened analysis of an algorithm for dominating set in planar graphs ⋮ On independent sets and bicliques in graphs ⋮ Capacitated domination faster than \(O(2^n)\) ⋮ An exact exponential time algorithm for \textsc{Power} \textsc{Dominating} \textsc{Set} ⋮ Exact algorithms for edge domination ⋮ Simplifying Inclusion–Exclusion Formulas ⋮ Breaking the \(2^{n}\)-barrier for irredundance: two lines of attack ⋮ An exact algorithm for connected red-blue dominating set ⋮ Bicolored independent sets and bicliques ⋮ On partitioning a graph into two connected subgraphs ⋮ Computing the differential of a graph: hardness, approximability and exact algorithms ⋮ A note on the independence number, domination number and related parameters of random binary search trees and random recursive trees ⋮ Solving the 2-disjoint connected subgraphs problem faster than \(2^n\) ⋮ Exact algorithms for minimum weighted dominating induced matching ⋮ Inclusion/exclusion meets measure and conquer ⋮ Scheduling partially ordered jobs faster than \(2^n\) ⋮ Parameterized measure \& conquer for problems with no small kernels ⋮ Solving Capacitated Dominating Set by Using Covering by Subsets and Maximum Matching ⋮ Inclusion/Exclusion Branching for Partial Dominating Set and Set Splitting

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