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)

Cites Work

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

Cited In (10)

Parameterized complexity of the weighted independent set problem beyond graphs of bounded clique number
Collaborating with Hans: Some Remaining Wonderments
Parameterized complexity of finding subgraphs with hereditary properties on hereditary graph classes
Title not available (Why is that?)
Fixed cardinality stable sets
Parameterized algorithms for Max Colorable Induced Subgraph problem on perfect graphs
Parameterized inapproximability of independent set in \(H\)-free graphs
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.

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)