Parameterized Complexity of Independent Set in H-Free Graphs.

DOI10.4230/LIPICS.IPEC.2018.17OpenAlexW2964160217MaRDI QIDQ5009479

Édouard Bonnet, Pierre Charbit, Rémi Watrigant, Steéphan Thomassé, Nicolas Bousquet

Publication date: 4 August 2021

Full work available at URL: https://doi.org/10.4230/LIPIcs.IPEC.2018.17

zbMATH Keywords

independent setparameterized algorithmsH-free graphs

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Algorithms in computer science (68Wxx)

Related Items (9)

Parameterized complexity of finding subgraphs with hereditary properties on hereditary graph classes ⋮ 1-extendability of independent sets ⋮ The homogeneous broadcast problem in narrow and wide strips. II: Lower bounds ⋮ Galactic token sliding ⋮ Token sliding on graphs of girth five ⋮ Grundy Coloring and friends, half-graphs, bicliques ⋮ Unnamed Item ⋮ On girth and the parameterized complexity of token sliding and Token Jumping ⋮ Revising Johnson's table for the 21st century

Cites Work

• Unnamed Item
• Unnamed Item
• Maximum weight independent sets in classes related to claw-free graphs
• Fundamentals of parameterized complexity
• Parameterized complexity of the weighted independent set problem beyond graphs of bounded clique number
• Parameterized complexity of induced graph matching on claw-free graphs
• A polynomial Turing-kernel for weighted independent set in bull-free graphs
• Finding odd cycle transversals.
• Improved FPT algorithms for weighted independent set in bull-free graphs
• Independent sets in some classes of \(S_{i,j,k}\)-free graphs
• Iterative Expansion and Color Coding
• Independent Set in P₅-Free Graphs in Polynomial Time
• Parameterized Algorithms

This page was built for publication: Parameterized Complexity of Independent Set in H-Free Graphs.