Improved FPT algorithms for weighted independent set in bull-free graphs

DOI10.1016/J.DISC.2017.09.012MaRDI QIDQ1685998zbMATH OpenOpenAlexFDO

Authors Henri Perret du Cray, Ignasi Sau

Publication date 20 December 2017

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.disc.2017.09.012

zbMATH Keywords

FPT algorithmindependent setparameterized complexitybull-free graphsTuring kernel

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Coloring of graphs and hypergraphs (05C15)

Recommendations

• Improved FPT Algorithms for Weighted Independent Set in Bull-Free Graphs
• A polynomial Turing-kernel for weighted independent set in bull-free graphs
• A polynomial Turing-kernel for weighted independent set in bull-free graphs
• Coloring bull-free perfect graphs
• Maximum Weight Independent Sets in ( $$S_{1,1,3}$$ , bull)-free Graphs

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 3445275 (Why is no real title available?)
• scientific article; zbMATH DE number 2203240 (Why is no real title available?)
• scientific article; zbMATH DE number 2234775 (Why is no real title available?)
• A polynomial Turing-kernel for weighted independent set in bull-free graphs
• Computing independent sets in graphs with large girth
• Dominating set is fixed parameter tractable in claw-free graphs
• Fundamentals of parameterized complexity
• Graph minors. XVI: Excluding a non-planar graph
• Lower bounds based on the exponential time hypothesis
• New lower bounds on independence number in triangle-free graphs in terms of order, maximum degree and girth
• On the subexponential-time complexity of CSP
• Parameterized algorithms
• Parameterized complexity of induced \(H\)-matching on claw-free graphs
• Parameterized complexity of the weighted independent set problem beyond graphs of bounded clique number
• Parametrized complexity theory.
• Partitioning a graph into disjoint cliques and a triangle-free graph
• The complexity of partitioning into disjoint cliques and a triangle-free graph
• The structure of bull-free graphs I -- three-edge-paths with centers and anticenters
• The structure of bull-free graphs II and III -- a summary
• The structure of claw-free graphs

Cited in

(6)

• Parameterized algorithms for Max Colorable Induced Subgraph problem on perfect graphs
• Improved FPT Algorithms for Weighted Independent Set in Bull-Free Graphs
• Parameterized complexity of independent set in H-free graphs
• A polynomial Turing-kernel for weighted independent set in bull-free graphs
• A polynomial Turing-kernel for weighted independent set in bull-free graphs
• Parameterized complexity of independent set in \(H\)-free graphs

This page was built for publication: Improved FPT algorithms for weighted independent set in bull-free graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1685998)