Improved parameterized set splitting algorithms: A Probabilistic approach
From MaRDI portal
Publication:1040647
DOI10.1007/s00453-008-9206-yzbMath1192.68854OpenAlexW2034597127MaRDI QIDQ1040647
Publication date: 25 November 2009
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00453-008-9206-y
Related Items (9)
Dealing with several parameterized problems by random methods ⋮ Matching and weighted \(P_2\)-packing: algorithms and kernels ⋮ Improved Parameterized Algorithms for Weighted 3-Set Packing ⋮ An \(O^{*}(3.53^{3k})\)-time parameterized algorithm for the 3-set packing problem ⋮ Improved Algorithms for Several Parameterized Problems Based on Random Methods ⋮ Inclusion/exclusion meets measure and conquer ⋮ Inclusion/Exclusion Branching for Partial Dominating Set and Set Splitting ⋮ Randomized parameterized algorithms for \(P_2\)-packing and co-path packing problems ⋮ Randomized fixed-parameter algorithms for the closest string problem
Uses Software
Cites Work
- Better approximation algorithms for \textsc{Set Splitting} and \textsc{Not-All-Equal Sat}
- Approximability of maximum splitting of k-sets and some other Apx-complete problems
- Improved exact algorithms for MAX-SAT
- Outward rotations
- Divide-and-Color
- Improved Algorithms for Weighted and Unweighted Set Splitting Problems
- Storing a Sparse Table with 0 (1) Worst Case Access Time
- A fast and simple randomized parallel algorithm for the maximal independent set problem
- Parameterized and Exact Computation
- Graph-Theoretic Concepts in Computer Science
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: Improved parameterized set splitting algorithms: A Probabilistic approach
