Set partitioning via inclusion-exclusion
From MaRDI portal
Publication:3558013
DOI10.1137/070683933zbMATH Open1215.05056OpenAlexW2074359677WikidataQ55881118 ScholiaQ55881118MaRDI QIDQ3558013FDOQ3558013
Authors: Andreas Björklund, Thore Husfeldt, Mikko Koivisto 
Publication date: 29 April 2010
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/070683933
Recommendations
Graph theory (including graph drawing) in computer science (68R10) Combinatorial optimization (90C27) Coloring of graphs and hypergraphs (05C15) General topics in the theory of algorithms (68W01)
Cited In (only showing first 100 items - show all)
- An exponential time 2-approximation algorithm for bandwidth
- On exact algorithms for the permutation CSP
- Tight lower bounds for the complexity of multicoloring
- Sharp separation and applications to exact and parameterized algorithms
- The parameterized complexity of the rainbow subgraph problem
- The parameterized complexity of the rainbow subgraph problem
- Chromatic kernel and its applications
- Fine-grained parameterized complexity analysis of graph coloring problems
- Partition into triangles on bounded degree graphs
- Set multi-covering via inclusion-exclusion
- Efficient approximation of Min Set Cover by moderately exponential algorithms
- New exact algorithms for the 2-constraint satisfaction problem
- Simplifying Inclusion–Exclusion Formulas
- On the parameterized complexity of compact set packing
- Counting problems in parameterized complexity
- New Plain-Exponential Time Classes for Graph Homomorphism
- Counting independent sets in claw-free graphs
- Assigning channels via the meet-in-the-middle approach
- An exact exponential time algorithm for counting bipartite cliques
- Computing hypergraph width measures exactly
- Parameterized pre-coloring extension and list coloring problems
- Fine-grained complexity of the graph homomorphism problem for bounded-treewidth graphs
- Computing the chromatic number using graph decompositions via matrix rank
- Exponential-time quantum algorithms for graph coloring problems
- Complexity and approximability of optimal resource allocation and Nash equilibrium over networks
- Fine-grained parameterized complexity analysis of graph coloring problems
- A Faster Exponential Time Algorithm for Bin Packing With a Constant Number of Bins via Additive Combinatorics
- Dynamic programming based algorithms for set multicover and multiset multicover problems
- Fast polynomial-space algorithms using inclusion-exclusion. Improving on Steiner tree and related problems
- Counting perfect matchings as fast as Ryser
- Enumerating the edge-colourings and total colourings of a regular graph
- Rural postman parameterized by the number of components of required edges
- Dual parameterization of weighted coloring
- Dual parameterization of weighted coloring
- Breaking the \(2^{n}\)-barrier for irredundance: two lines of attack
- A hybrid exact algorithm for complete set partitioning
- Regular inference as vertex coloring
- Lower bounds for the graph homomorphism problem
- Parameterized and exact algorithms for class domination coloring
- Fast zeta transforms for lattices with few irreducibles
- Feedback vertex sets in tournaments
- Nonuniform ACC circuit lower bounds
- Narrow sieves for parameterized paths and packings
- Strong valid inequalities for Boolean logical pattern generation
- Approximating MAX SAT by moderately exponential and parameterized algorithms
- Title not available (Why is that?)
- Efficient Approximation of Combinatorial Problems by Moderately Exponential Algorithms
- Coalition structure generation: a survey
- On the parameterized complexity of b-\textsc{chromatic number}
- Channel assignment via fast zeta transform
- Solving the 2-disjoint connected subgraphs problem faster than \(2^n\)
- NP-completeness results for partitioning a graph into total dominating sets
- New plain-exponential time classes for graph homomorphism
- When polynomial approximation meets exact computation
- Trimmed Moebius inversion and graphs of bounded degree
- On partitioning a graph into two connected subgraphs
- Efficient algorithms for the \textsc{max~\(k\)-vertex cover problem}
- Exact algorithms for counting 3-colorings of graphs
- Multivariate analysis of orthogonal range searching and graph distances
- New potential functions for greedy independence and coloring
- Families with infants: a general approach to solve hard partition problems
- Counting Maximal Independent Sets in Subcubic Graphs
- When polynomial approximation meets exact computation
- Algebraic methods in the congested clique
- Notes on tree- and path-chromatic number
- On subexponential and FPT-time inapproximability
- BIPARTITIONING INTO OVERLAPPING SETS
- An initial study of time complexity in infinite-domain constraint satisfaction
- Solving the train marshalling problem by inclusion-exclusion
- Solving SCS for bounded length strings in fewer than \(2^n\) steps
- Exact algorithm for graph homomorphism and locally injective graph homomorphism
- Inclusion/exclusion meets measure and conquer
- On maximal chain subgraphs and covers of bipartite graphs
- On independent sets and bicliques in graphs
- Scheduling partially ordered jobs faster than \(2^n\)
- Title not available (Why is that?)
- Dominator coloring and CD coloring in almost cluster graphs
- Fixed-parameter tractability of \((n-k)\) list coloring
- Parameterized complexity of the workflow satisfiability problem
- Determining the \(L(2,1)\)-span in polynomial space
- Solving the list coloring problem through a branch-and-price algorithm
- Title not available (Why is that?)
- Finding disjoint paths in networks with star shared risk link groups
- Fine-Grained Reductions and Quantum Speedups for Dynamic Programming.
- A branch and price algorithm for list coloring problem
- Title not available (Why is that?)
- Complexity of fall coloring for restricted graph classes
- Harmonious coloring: parameterized algorithms and upper bounds
- Algorithms for dominating clique problems
- Parameterized exact and approximation algorithms for maximum \(k\)-set cover and related satisfiability problems
- Improved algorithm to determine 3-colorability of graphs with minimum degree at least 7
- A complexity dichotomy for critical values of the b-chromatic number of graphs
- Title not available (Why is that?)
- Tensor network complexity of multilinear maps
- Title not available (Why is that?)
- On the parameterized complexity of compact set packing
- Invitation to Algorithmic Uses of Inclusion–Exclusion
- Testing the Complexity of a Valued CSP Language
- Faster exponential-time algorithms in graphs of bounded average degree
- Computing generalized convolutions faster than brute force
This page was built for publication: Set partitioning via inclusion-exclusion
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3558013)
