Improved Algorithms for Several Parameterized Problems Based on Random Methods
From MaRDI portal
Publication:4632170
DOI10.1007/978-3-319-39817-4_7zbMath1475.68462OpenAlexW2492498253MaRDI QIDQ4632170
Qilong Feng, Xiong Jiang, Jianxin Wang
Publication date: 26 April 2019
Published in: Frontiers in Algorithmics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-319-39817-4_7
Analysis of algorithms (68W40) Graph theory (including graph drawing) in computer science (68R10) Randomized algorithms (68W20) Parameterized complexity, tractability and kernelization (68Q27)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Improved deterministic algorithms for weighted matching and packing problems
- Improved parameterized set splitting algorithms: A Probabilistic approach
- Maximum bounded \(H\)-matching is Max SNP-complete
- Narrow sieves for parameterized paths and packings
- Packing paths: recycling saves time
- Parameterized algorithms for load coloring problem
- On the minimum load coloring problem
- An approximation algorithm for maximum triangle packing
- Polynomial Kernelization for Removing Induced Claws and Diamonds
- Parameterized Algorithms for Module Motif
- On the Complexity of General Graph Factor Problems
- On the Size of Systems of Sets Every t of which Have an SDR, with an Application to the Worst-Case Ratio of Heuristics for Packing Problems
- On the completeness of a generalized matching problem
- Fixed-parameter tractability of multicut parameterized by the size of the cutset
- Graph-Theoretic Concepts in Computer Science
