Inclusion/exclusion meets measure and conquer
From MaRDI portal
Publication:2249747
DOI10.1007/s00453-013-9759-2zbMath1291.68441OpenAlexW2136595209MaRDI QIDQ2249747
Johan M. M. van Rooij, Thomas C. van Dijk, Jesper Nederlof
Publication date: 3 July 2014
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00453-013-9759-2
Analysis of algorithms (68W40) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items (5)
Separate, Measure and Conquer: Faster Polynomial-Space Algorithms for Max 2-CSP and Counting Dominating Sets ⋮ Roman domination in subgraphs of grids ⋮ Exact Algorithms for the Minimum Load Spanning Tree Problem ⋮ NP-completeness results for partitioning a graph into total dominating sets ⋮ Exact algorithms for counting 3-colorings of graphs
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Better approximation algorithms for \textsc{Set Splitting} and \textsc{Not-All-Equal Sat}
- Exact algorithms for dominating set
- A universally fastest algorithm for Max 2-sat, Max 2-CSP, and everything in between
- Exact exponential algorithms.
- On partitioning a graph into two connected subgraphs
- An exact algorithm for the maximum leaf spanning tree problem
- Implicit branching and parameterized partial cover problems
- Inclusion and exclusion algorithm for the Hamiltonian path problem
- An improved exact algorithm for the domatic number problem
- Solving connected dominating set faster than \(2^n\)
- Exact algorithms for exact satisfiability and number of perfect matchings
- On the minimum feedback vertex set problem: Exact and enumeration algorithms
- Efficiency in exponential time for domination-type problems
- On two techniques of combining branching and treewidth
- Improved parameterized set splitting algorithms: A Probabilistic approach
- Dynamic programming meets the principle of inclusion and exclusion
- A partial k-arboretum of graphs with bounded treewidth
- Algorithms for dominating clique problems
- Improved approximations for max set splitting and max NAE SAT
- Subexponential algorithms for partial cover problems
- Covering and packing in linear space
- Exact algorithms for edge domination
- Trimmed Moebius inversion and graphs of bounded degree
- Fast algorithms for max independent set
- On independent sets and bicliques in graphs
- A note on the complexity of minimum dominating set
- The intersection graphs of subtrees in trees are exactly the chordal graphs
- Outward rotations
- A Faster Algorithm for Dominating Set Analyzed by the Potential Method
- Quasiconvex analysis of multivariate recurrence equations for backtracking algorithms
- Enumerate and Measure: Improving Parameter Budget Management
- Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs
- A measure & conquer approach for the analysis of exact algorithms
- Fourier meets M\"{o}bius: fast subset convolution
- Set Partitioning via Inclusion-Exclusion
- Maximum Independent Set in Graphs of Average Degree at Most Three in ${\mathcal O}(1.08537^n)$
- Fast Algorithms for min independent dominating set
- Limits and Applications of Group Algebras for Parameterized Problems
- Inclusion/Exclusion Meets Measure and Conquer
- Dynamic Programming on Tree Decompositions Using Generalised Fast Subset Convolution
- Counting Paths and Packings in Halves
- Even Faster Algorithm for Set Splitting!
- Improved bounds and algorithms for hypergraph 2-coloring
- On Problems as Hard as CNF-SAT
- Combinatorial bounds via measure and conquer
- A Bound on the Pathwidth of Sparse Graphs with Applications to Exact Algorithms
- Parameterized and Exact Computation
- Partial vs. Complete Domination: t-Dominating Set
- Mathematical Foundations of Computer Science 2005
- On a combinatorial problem. II
- Graph-Theoretic Concepts in Computer Science
- Counting Subgraphs via Homomorphisms
- SOFSEM 2006: Theory and Practice of Computer Science
- Graph-Theoretic Concepts in Computer Science
This page was built for publication: Inclusion/exclusion meets measure and conquer
