Improved FPT algorithms for weighted independent set in bull-free graphs
From MaRDI portal
Publication:1685998
DOI10.1016/J.DISC.2017.09.012zbMATH Open1376.05155OpenAlexW2763138650MaRDI QIDQ1685998FDOQ1685998
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
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
Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Coloring of graphs and hypergraphs (05C15)
Cites Work
- Fundamentals of parameterized complexity
- Title not available (Why is that?)
- Parametrized complexity theory.
- Lower bounds based on the exponential time hypothesis
- Title not available (Why is that?)
- Parameterized algorithms
- Title not available (Why is that?)
- 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
- On the subexponential-time complexity of CSP
- Title not available (Why is that?)
- Graph minors. XVI: Excluding a non-planar graph
- Parameterized complexity of the weighted independent set problem beyond graphs of bounded clique number
- New lower bounds on independence number in triangle-free graphs in terms of order, maximum degree and girth
- Computing independent sets in graphs with large girth
- Domination when the stars are out
- Parameterized complexity of induced \(H\)-matching on claw-free graphs
- Dominating set is fixed parameter tractable in claw-free graphs
- Partitioning a graph into disjoint cliques and a triangle-free graph
- The complexity of partitioning into disjoint cliques and a triangle-free graph
- A polynomial Turing-kernel for weighted independent set in bull-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
- A polynomial Turing-kernel 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
- 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)
