Set Partitioning via Inclusion-Exclusion
From MaRDI portal
Publication:3558013
DOI10.1137/070683933zbMath1215.05056OpenAlexW2074359677WikidataQ55881118 ScholiaQ55881118MaRDI QIDQ3558013
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
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)
Related Items (only showing first 100 items - show all)
Some Cardinal Estimations via the Inclusion-Exclusion Principle in Finite $$T_0$$ Topological Spaces ⋮ A Faster Exponential Time Algorithm for Bin Packing With a Constant Number of Bins via Additive Combinatorics ⋮ On the parameterized complexity of compact set packing ⋮ Star covers and star partitions of double-split graphs ⋮ Dominator coloring and CD coloring in almost cluster graphs ⋮ Unnamed Item ⋮ Computing generalized convolutions faster than brute force ⋮ Unnamed Item ⋮ When polynomial approximation meets exact computation ⋮ When polynomial approximation meets exact computation ⋮ NP-completeness results for partitioning a graph into total dominating sets ⋮ Complexity of fall coloring for restricted graph classes ⋮ Fixed-parameter tractability of \((n-k)\) list coloring ⋮ Faster graph coloring in polynomial space ⋮ Complexity and Approximability of Optimal Resource Allocation and Nash Equilibrium over Networks ⋮ Parameterized Pre-Coloring Extension and List Coloring Problems ⋮ Fine-Grained Complexity of the Graph Homomorphism Problem for Bounded-Treewidth Graphs ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Exponential-time quantum algorithms for graph coloring problems ⋮ Fine-Grained Parameterized Complexity Analysis of Graph Coloring Problems ⋮ Counting Maximal Independent Sets in Subcubic Graphs ⋮ Assigning channels via the meet-in-the-middle approach ⋮ A branch and price algorithm for list coloring problem ⋮ Set multi-covering via inclusion-exclusion ⋮ Lower Bounds for the Graph Homomorphism Problem ⋮ Harmonious coloring: parameterized algorithms and upper bounds ⋮ Rural postman parameterized by the number of components of required edges ⋮ Harmonious Coloring: Parameterized Algorithms and Upper Bounds ⋮ Efficient Approximation of Combinatorial Problems by Moderately Exponential Algorithms ⋮ Nonuniform ACC Circuit Lower Bounds ⋮ On the parameterized complexity of b-\textsc{chromatic number} ⋮ Partition into triangles on bounded degree graphs ⋮ Induced star partition of graphs ⋮ Narrow sieves for parameterized paths and packings ⋮ Parameterized and exact algorithms for class domination coloring ⋮ List-coloring -- parameterizing from triviality ⋮ Strong valid inequalities for Boolean logical pattern generation ⋮ The Parameterized Complexity of the Rainbow Subgraph Problem ⋮ An exponential time 2-approximation algorithm for bandwidth ⋮ On exact algorithms for the permutation CSP ⋮ Exact and superpolynomial approximation algorithms for the \textsc{densest \textit{K}-subgraph} problem ⋮ Parameterized approximation via fidelity preserving transformations ⋮ Parameterized complexity of happy coloring problems ⋮ Parameterized exact and approximation algorithms for maximumk-set cover and related satisfiability problems ⋮ On the complexity of restoring corrupted colorings ⋮ Coalition structure generation: a survey ⋮ A hybrid exact algorithm for complete set partitioning ⋮ On independent sets and bicliques in graphs ⋮ Channel assignment via fast zeta transform ⋮ Covering and packing in linear space ⋮ Sharp separation and applications to exact and parameterized algorithms ⋮ Fixing improper colorings of graphs ⋮ Tight Lower Bounds for the Complexity of Multicoloring ⋮ Simplifying Inclusion–Exclusion Formulas ⋮ Breaking the \(2^{n}\)-barrier for irredundance: two lines of attack ⋮ Unnamed Item ⋮ Fast polynomial-space algorithms using inclusion-exclusion. Improving on Steiner tree and related problems ⋮ An exact exponential time algorithm for counting bipartite cliques ⋮ Computing hypergraph width measures exactly ⋮ Parameterized and Exact Algorithms for Class Domination Coloring ⋮ Feedback Vertex Sets in Tournaments ⋮ New plain-exponential time classes for graph homomorphism ⋮ New exact algorithms for the 2-constraint satisfaction problem ⋮ Decomposition of realizable fuzzy relations ⋮ Enumerating the edge-colourings and total colourings of a regular graph ⋮ Trimmed Moebius inversion and graphs of bounded degree ⋮ On partitioning a graph into two connected subgraphs ⋮ Exact algorithm for graph homomorphism and locally injective graph homomorphism ⋮ Determining the \(L(2,1)\)-span in polynomial space ⋮ Solving SCS for bounded length strings in fewer than \(2^n\) steps ⋮ Regular inference as vertex coloring ⋮ Unnamed Item ⋮ Approximating MAX SAT by moderately exponential and parameterized algorithms ⋮ Why Is Maximum Clique Often Easy in Practice? ⋮ Solving the 2-disjoint connected subgraphs problem faster than \(2^n\) ⋮ Efficient algorithms for the \textsc{max~\(k\)-vertex cover problem} ⋮ The parameterized complexity of the rainbow subgraph problem ⋮ Dual parameterization of Weighted Coloring ⋮ Computing the Chromatic Number Using Graph Decompositions via Matrix Rank ⋮ Invitation to Algorithmic Uses of Inclusion–Exclusion ⋮ An initial study of time complexity in infinite-domain constraint satisfaction ⋮ Solving the train marshalling problem by inclusion-exclusion ⋮ Anticoncentration versus the Number of Subset Sums ⋮ Inclusion/exclusion meets measure and conquer ⋮ Scheduling partially ordered jobs faster than \(2^n\) ⋮ Algorithms for dominating clique problems ⋮ New potential functions for greedy independence and coloring ⋮ Algebraic methods in the congested clique ⋮ Dynamic programming based algorithms for set multicover and multiset multicover problems ⋮ New tools and connections for exponential-time approximation ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Improved algorithm to determine 3-colorability of graphs with minimum degree at least 7 ⋮ Inclusion/Exclusion Branching for Partial Dominating Set and Set Splitting ⋮ Parameterized Complexity of the Workflow Satisfiability Problem ⋮ Partition into Triangles on Bounded Degree Graphs ⋮ Unnamed Item ⋮ On Maximal Chain Subgraphs and Covers of Bipartite Graphs ⋮ Efficient approximation of Min Set Cover by moderately exponential algorithms
This page was built for publication: Set Partitioning via Inclusion-Exclusion
