Parameterized algorithms for the independent set problem in some hereditary graph classes

Analysis of algorithms and problem complexity (68Q25) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Recommendations

Parameterized complexity of the weighted independent set problem beyond graphs of bounded clique number
Parameterized complexity of the maximum independent set problem and the speed of hereditary properties
Parameterized complexity of independent set in H-free graphs
Parameterized complexity of independent set in \(H\)-free graphs
The Maximum Independent Set Problem in Planar Graphs

Cites work

scientific article; zbMATH DE number 3908482 (Why is no real title available?)
scientific article; zbMATH DE number 910871 (Why is no real title available?)
An augmenting graph approach to the stable set problem in \(P_{5}\)-free graphs
Augmenting graphs for independent sets
Computing independent sets in graphs with large girth
Exponential speedup of fixed-parameter algorithms for classes of graphs excluding single-crossing graphs as minors
Fixed Parameter Tractability of Independent Set in Segment Intersection Graphs
Geometric algorithms and combinatorial optimization
Linear time solvable optimization problems on graphs of bounded clique-width
Modular decomposition and transitive orientation
On clique separators, nearly chordal graphs, and the Maximum Weight Stable Set Problem
On finding augmenting graphs
On maximal independent sets of vertices in claw-free graphs
On the X-join decomposition for undirected graphs
On the homogeneous representation of interval graphs
On the parameterized complexity of multiple-interval graph problems
Parameterized complexity of the maximum independent set problem and the speed of hereditary properties
Paths, Trees, and Flowers
Polynomial algorithm for finding the largest independent sets in graphs without forks
Primitivity is hereditary for 2-structures
Simpler Linear-Time Modular Decomposition Via Recursive Factorizing Permutations
Solving some NP-complete problems using split decomposition
Stability preserving transformations of graphs
Stable sets in certain \(P_6\)-free graphs
TWO THEOREMS IN GRAPH THEORY
The independence number of graphs with large odd girth
Transitiv orientierbare Graphen
Triangles, 4-Cycles and Parameterized (In-)Tractability

Cited in

(14)

Collaborating with Hans: Some Remaining Wonderments
Parameterized complexity of independent set in \(H\)-free graphs
scientific article; zbMATH DE number 1405687 (Why is no real title available?)
Parameterized complexity of independent set in H-free graphs
On generalizations of the shadow independent set problem
Parameterized inapproximability of independent set in \(H\)-free graphs
Parameterized complexity of the weighted independent set problem beyond graphs of bounded clique number
Parameterized complexity of the maximum independent set problem and the speed of hereditary properties
On easy and hard hereditary classes of graphs with respect to the independent set problem
Getting linear time in graphs of bounded neighborhood diversity
Parameterized complexity of finding subgraphs with hereditary properties on hereditary graph classes
Parameterized complexity of finding subgraphs with hereditary properties.
Fixed cardinality stable sets
Parameterized algorithms for Max Colorable Induced Subgraph problem on perfect graphs

This page was built for publication: Parameterized algorithms for the independent set problem in some hereditary graph classes

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