Improved parameterized set splitting algorithms: A Probabilistic approach

DOI10.1007/s00453-008-9206-yzbMath1192.68854OpenAlexW2034597127MaRDI QIDQ1040647

Songjian Lu, Jian'er Chen

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

zbMATH Keywords

randomized algorithmderandomizationset splittingparametrized algorithm

Mathematics Subject Classification ID

Nonnumerical algorithms (68W05) Randomized algorithms (68W20)

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

• Outward rotations

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}
• 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

This page was built for publication: Improved parameterized set splitting algorithms: A Probabilistic approach