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

DOI10.1016/J.JDA.2011.12.012MaRDI QIDQ450563zbMATH OpenOpenAlexFDO

Authors Vadim Lozin, Haiko Müller, Dieter Rautenbach, Konrad 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

modular decompositionfixed-parameter tractabilityindependent sethereditary 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)

Recommendations

• Parameterized algorithms for the independent set problem in some hereditary graph classes
• On the Maximum Weight Clique Problem
• Parameterized complexity of the maximum independent set problem and the speed of hereditary properties
• Maximum weight independent sets in classes related to claw-free graphs
• Parameterized complexity of independent set in H-free graphs

Cites work

• scientific article; zbMATH DE number 3908482 (Why is no real title available?)
• scientific article; zbMATH DE number 1161563 (Why is no real title available?)
• A New Algorithm for Generating All the Maximal Independent Sets
• Applying modular decomposition to parameterized cluster editing problems
• 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 graphs with polynomially solvable maximum-weight clique problem
• 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 algorithms for the independent set problem in some hereditary graph classes
• Parameterized complexity of the maximum independent set problem and the speed of hereditary properties
• Paw-free graphs
• 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
• The speed of hereditary properties of graphs
• Transitiv orientierbare Graphen
• Triangles, 4-Cycles and Parameterized (In-)Tractability

Cited in

(12)

• 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
• Parameterized complexity of independent set in H-free graphs
• 1-extendability of independent sets
• Inductive \(k\)-independent graphs and \(c\)-colorable subgraphs in scheduling: a review
• Parameterized algorithms for the independent set problem in some hereditary graph classes
• Parameterized complexity of the maximum independent set problem and the speed of hereditary properties
• A polynomial Turing-kernel for weighted independent set in bull-free graphs
• Complexity results for rainbow matchings
• Fixed cardinality stable sets
• 1-extendability of independent sets

This page was built for publication: Parameterized complexity of the weighted independent set problem beyond graphs of bounded clique number

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