Parameterized complexity of the weighted independent set problem beyond graphs of bounded clique number

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

zbMATH Keywords

independent setmodular decompositionfixed-parameter tractabilityhereditary class of graphs

Mathematics Subject Classification ID

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