Parameterized Algorithms for the Independent Set Problem in Some Hereditary Graph Classes
From MaRDI portal
Publication:3000488
DOI10.1007/978-3-642-19222-7_1zbMath1295.68131OpenAlexW1497268659MaRDI QIDQ3000488
Haiko Müller, Konrad K. Dabrowski, Dieter Rautenbach, Vadim V. Lozin
Publication date: 19 May 2011
Published in: Lecture Notes in Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-642-19222-7_1
Analysis of algorithms and problem complexity (68Q25) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)
Related Items (6)
Collaborating with Hans: Some Remaining Wonderments ⋮ Parameterized complexity of finding subgraphs with hereditary properties on hereditary graph classes ⋮ Parameterized complexity of the weighted independent set problem beyond graphs of bounded clique number ⋮ Fixed cardinality stable sets ⋮ Parameterized algorithms for Max Colorable Induced Subgraph problem on perfect graphs ⋮ Parameterized inapproximability of independent set in \(H\)-free graphs
Cites Work
- Unnamed Item
- Unnamed Item
- Stability preserving transformations of graphs
- Augmenting graphs for independent sets
- Primitivity is hereditary for 2-structures
- Solving some NP-complete problems using split decomposition
- On finding augmenting graphs
- On the parameterized complexity of multiple-interval graph problems
- On maximal independent sets of vertices in claw-free graphs
- On the X-join decomposition for undirected graphs
- Computing independent sets in graphs with large girth
- Geometric algorithms and combinatorial optimization
- Modular decomposition and transitive orientation
- Stable sets in certain \(P_6\)-free graphs
- The independence number of graphs with large odd girth
- An augmenting graph approach to the stable set problem in \(P_{5}\)-free graphs
- Exponential speedup of fixed-parameter algorithms for classes of graphs excluding single-crossing graphs as minors
- Linear time solvable optimization problems on graphs of bounded clique-width
- On clique separators, nearly chordal graphs, and the Maximum Weight Stable Set Problem
- Parameterized complexity of the maximum independent set problem and the speed of hereditary properties
- TWO THEOREMS IN GRAPH THEORY
- Fixed Parameter Tractability of Independent Set in Segment Intersection Graphs
- Simpler Linear-Time Modular Decomposition Via Recursive Factorizing Permutations
- On the homogeneous representation of interval graphs
- Polynomial algorithm for finding the largest independent sets in graphs without forks
- Paths, Trees, and Flowers
- Transitiv orientierbare Graphen
- Triangles, 4-Cycles and Parameterized (In-)Tractability
This page was built for publication: Parameterized Algorithms for the Independent Set Problem in Some Hereditary Graph Classes
