Improved FPT algorithms for weighted independent set in bull-free graphs
From MaRDI portal
Publication:1685998
DOI10.1016/j.disc.2017.09.012zbMath1376.05155OpenAlexW2763138650MaRDI QIDQ1685998
Ignasi Sau, Henri Perret du Cray
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
Analysis of algorithms and problem complexity (68Q25) Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items
Parameterized Complexity of Independent Set in H-Free Graphs. ⋮ A polynomial Turing-kernel for weighted independent set in bull-free graphs ⋮ Parameterized algorithms for Max Colorable Induced Subgraph problem on perfect graphs ⋮ Parameterized complexity of independent set in H-free graphs
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Fundamentals of parameterized complexity
- New lower bounds on independence number in triangle-free graphs in terms of order, maximum degree and girth
- Parameterized complexity of the weighted independent set problem beyond graphs of bounded clique number
- The complexity of partitioning into disjoint cliques and a triangle-free graph
- A polynomial Turing-kernel for weighted independent set in bull-free graphs
- Dominating set is fixed parameter tractable in claw-free graphs
- 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
- Computing independent sets in graphs with large girth
- Graph minors. XVI: Excluding a non-planar graph
- Partitioning a graph into disjoint cliques and a triangle-free graph
- Parametrized complexity theory.
- Parameterized Complexity of Induced H-Matching on Claw-Free Graphs
- Domination When the Stars Are Out
- On the Subexponential-Time Complexity of CSP
- Parameterized Algorithms
