Dealing with several parameterized problems by random methods

DOI10.1016/j.tcs.2017.09.024zbMath1393.68131OpenAlexW2756563550MaRDI QIDQ2636503

Xiong Jiang, Neng Huang, Jianxin Wang, Qilong Feng

Publication date: 5 June 2018

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2017.09.024

zbMATH Keywords

random methodsparameterized \(P_3\)-packingparameterized claw-free edge deletionparameterized load coloring

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Randomized algorithms (68W20)

Related Items (5)

Improved PTAS for the constrained \(k\)-means problem ⋮ An improved kernel for max-bisection above tight lower bound ⋮ An approximation algorithm for the \(l\)-pseudoforest deletion problem ⋮ On the complexity of algorithms for detecting \(k\)-length negative cost cycles ⋮ An improved linear kernel for complementary maximal strip recovery: simpler and smaller

Cites Work

• Unnamed Item
• Unnamed Item
• Partition on trees with supply and demand: kernelization and algorithms
• Improved kernel results for some FPT problems based on simple observations
• Improved deterministic algorithms for weighted matching and packing problems
• Approximating maximum agreement forest on multiple binary trees
• Deeper local search for parameterized and approximation algorithms for maximum internal spanning tree
• Improved parameterized set splitting algorithms: A Probabilistic approach
• Fixed-parameter complexity in AI and nonmonotonic reasoning
• Parameterized computational complexity of Dodgson and Young elections
• Narrow sieves for parameterized paths and packings
• Parameterized and approximation algorithms for the load coloring problem
• Packing paths: recycling saves time
• Parameterized algorithms for load coloring problem
• On the minimum load coloring problem
• Polynomial Kernelization for Removing Induced Claws and Diamonds
• 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
• Scheduling Split Intervals
• Parameterized Algorithms
• Graph-Theoretic Concepts in Computer Science

This page was built for publication: Dealing with several parameterized problems by random methods