Parameterized complexity of the weighted independent set problem beyond graphs of bounded clique number
DOI10.1016/J.JDA.2011.12.012zbMATH Open1247.68109OpenAlexW2088153883MaRDI QIDQ450563FDOQ450563
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
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
Analysis of algorithms and problem complexity (68Q25) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)
Cites Work
- Geometric algorithms and combinatorial optimization
- Applying modular decomposition to parameterized cluster editing problems
- Modular decomposition and transitive orientation
- Linear time solvable optimization problems on graphs of bounded clique-width
- A New Algorithm for Generating All the Maximal Independent Sets
- Title not available (Why is that?)
- Transitiv orientierbare Graphen
- On maximal independent sets of vertices in claw-free graphs
- On the parameterized complexity of multiple-interval graph problems
- Paw-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
- The speed of hereditary properties of graphs
- Simpler Linear-Time Modular Decomposition Via Recursive Factorizing Permutations
- Title not available (Why is that?)
- On graphs with polynomially solvable maximum-weight clique problem
- 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
- Parameterized algorithms for the independent set problem in some hereditary graph classes
- Fixed Parameter Tractability of Independent Set in Segment Intersection Graphs
- Triangles, 4-Cycles and Parameterized (In-)Tractability
- Stability preserving transformations of graphs
Cited In (11)
- Colouring of graphs with Ramsey-type forbidden subgraphs
- Improved FPT algorithms for weighted independent set in bull-free graphs
- 1-extendability of independent sets
- Fixed cardinality stable sets
- Complexity results for rainbow matchings
- Parameterized Complexity of Independent Set in H-Free Graphs.
- 1-extendability of independent sets
- Parameterized algorithms for the independent set problem in some hereditary graph classes
- Parameterized complexity of independent set in H-free graphs
- A polynomial Turing-kernel for weighted independent set in bull-free graphs
- Parameterized complexity of the maximum independent set problem and the speed of hereditary properties
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)
