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

DOI10.1016/J.DISC.2017.09.012zbMATH Open1376.05155OpenAlexW2763138650MaRDI QIDQ1685998FDOQ1685998

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

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)

Cites Work

• Fundamentals of parameterized complexity
• Title not available (Why is that?)
• Parametrized complexity theory.
• Title not available (Why is that?)
• 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
• Title not available (Why is that?)
• 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 (5)

• 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.
• Parameterized complexity of independent set in H-free graphs
• A polynomial Turing-kernel for weighted independent set in bull-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)