Parameterized complexity of the weighted independent set problem beyond graphs of bounded clique number
From MaRDI portal
Publication:450563
DOI10.1016/j.jda.2011.12.012zbMath1247.68109OpenAlexW2088153883MaRDI QIDQ450563
Vadim V. Lozin, Haiko Müller, Dieter Rautenbach, Konrad K. Dabrowski
Publication date: 13 September 2012
Published in: Journal of Discrete Algorithms (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.jda.2011.12.012
Analysis of algorithms and problem complexity (68Q25) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)
Related Items (9)
Complexity results for rainbow matchings ⋮ 1-extendability of independent sets ⋮ Colouring of graphs with Ramsey-type forbidden subgraphs ⋮ Improved FPT algorithms for weighted independent set in bull-free graphs ⋮ Parameterized Complexity of Independent Set in H-Free Graphs. ⋮ Fixed cardinality stable sets ⋮ A polynomial Turing-kernel for weighted independent set in bull-free graphs ⋮ 1-extendability of independent sets ⋮ Parameterized complexity of independent set in H-free graphs
Cites Work
- Unnamed Item
- Unnamed Item
- Stability preserving transformations of graphs
- Primitivity is hereditary for 2-structures
- Solving some NP-complete problems using split decomposition
- On the parameterized complexity of multiple-interval graph problems
- Paw-free graphs
- 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
- Exponential speedup of fixed-parameter algorithms for classes of graphs excluding single-crossing graphs as minors
- The speed of hereditary properties of graphs
- Linear time solvable optimization problems on graphs of bounded clique-width
- Applying modular decomposition to parameterized cluster editing problems
- 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
- Parameterized Algorithms for the Independent Set Problem in Some Hereditary Graph Classes
- Fixed Parameter Tractability of Independent Set in Segment Intersection Graphs
- Simpler Linear-Time Modular Decomposition Via Recursive Factorizing Permutations
- On graphs with polynomially solvable maximum-weight clique problem
- On the homogeneous representation of interval graphs
- A New Algorithm for Generating All the Maximal Independent Sets
- Transitiv orientierbare Graphen
- Triangles, 4-Cycles and Parameterized (In-)Tractability
This page was built for publication: Parameterized complexity of the weighted independent set problem beyond graphs of bounded clique number