Set partitioning via inclusion-exclusion

DOI10.1137/070683933zbMATH Open1215.05056OpenAlexW2074359677WikidataQ55881118 ScholiaQ55881118MaRDI QIDQ3558013FDOQ3558013

Andreas Björklund, Mikko Koivisto, Thore Husfeldt

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

• Covering and Packing in Linear Space
• Covering and packing in linear space
• Inclusion/exclusion meets measure and conquer
• Partitioning into sets of bounded cardinality
• Exact Algorithms for Exact Satisfiability and Number of Perfect Matchings

zbMATH Keywords

exact algorithmgraph coloringset partitioninclusion-exclusionzeta transform

Mathematics Subject Classification ID

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
• Parameterized Pre-Coloring Extension and List Coloring Problems
• Title not available (Why is that?)
• Sharp separation and applications to exact and parameterized algorithms
• Fine-Grained Complexity of the Graph Homomorphism Problem for Bounded-Treewidth Graphs
• The parameterized complexity of the rainbow subgraph problem
• Fine-grained parameterized complexity analysis of graph coloring problems
• Complexity and Approximability of Optimal Resource Allocation and Nash Equilibrium over Networks
• Title not available (Why is that?)
• 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
• On Maximal Chain Subgraphs and Covers of Bipartite Graphs
• Simplifying Inclusion–Exclusion Formulas
• On the parameterized complexity of compact set packing
• Partition into Triangles on Bounded Degree Graphs
• New Plain-Exponential Time Classes for Graph Homomorphism
• Dual parameterization of Weighted Coloring
• Assigning channels via the meet-in-the-middle approach
• An exact exponential time algorithm for counting bipartite cliques
• Computing hypergraph width measures exactly
• Computing the chromatic number using graph decompositions via matrix rank
• Exponential-time quantum algorithms for graph coloring problems
• The Parameterized Complexity of the Rainbow Subgraph Problem
• 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
• 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
• Breaking the \(2^{n}\)-barrier for irredundance: two lines of attack
• A hybrid exact algorithm for complete set partitioning
• Partition into triangles on bounded degree graphs
• Regular inference as vertex coloring
• Narrow sieves for parameterized paths and packings
• Parameterized and Exact Algorithms for Class Domination Coloring
• Strong valid inequalities for Boolean logical pattern generation
• Counting Independent Sets in Claw-Free Graphs
• 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}
• Parameterized exact and approximation algorithms for maximumk-set cover and related satisfiability problems
• Channel assignment via fast zeta transform
• Tight Lower Bounds for the Complexity of Multicoloring
• 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
• Counting Maximal Independent Sets in Subcubic Graphs
• When polynomial approximation meets exact computation
• Algebraic methods in the congested clique
• Computing the Chromatic Number Using Graph Decompositions via Matrix Rank
• Notes on tree- and path-chromatic number
• On subexponential and FPT-time inapproximability
• Lower Bounds for the Graph Homomorphism Problem
• BIPARTITIONING INTO OVERLAPPING SETS
• Nonuniform ACC Circuit Lower Bounds
• Title not available (Why is that?)
• Feedback Vertex Sets in Tournaments
• 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
• Fine-Grained Parameterized Complexity Analysis of Graph Coloring Problems
• On independent sets and bicliques in graphs
• Scheduling partially ordered jobs faster than \(2^n\)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Dominator coloring and CD coloring in almost cluster graphs
• Fixed-parameter tractability of \((n-k)\) list coloring
• 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
• 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?)
• 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
• Tight Lower Bounds for List Edge Coloring
• 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)