Parameterized algorithms for the independent set problem in some hereditary graph classes

DOI10.1007/978-3-642-19222-7_1zbMATH Open1295.68131OpenAlexW1497268659MaRDI QIDQ3000488FDOQ3000488

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

Recommendations

• Parameterized complexity of the weighted independent set problem beyond graphs of bounded clique number
• Parameterized complexity of the maximum independent set problem and the speed of hereditary properties
• Parameterized complexity of independent set in H-free graphs
• Parameterized complexity of independent set in \(H\)-free graphs
• The Maximum Independent Set Problem in Planar Graphs

Mathematics Subject Classification ID

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
• Paths, Trees, and Flowers
• Modular decomposition and transitive orientation
• Linear time solvable optimization problems on graphs of bounded clique-width
• Transitiv orientierbare Graphen
• On maximal independent sets of vertices in claw-free graphs
• TWO THEOREMS IN GRAPH THEORY
• Title not available (Why is that?)
• On finding augmenting graphs
• On the parameterized complexity of multiple-interval graph problems
• Stable sets in certain \(P_6\)-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
• An augmenting graph approach to the stable set problem in \(P_{5}\)-free graphs
• Polynomial algorithm for finding the largest independent sets in graphs without forks
• Simpler Linear-Time Modular Decomposition Via Recursive Factorizing Permutations
• Title not available (Why is that?)
• 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
• Fixed Parameter Tractability of Independent Set in Segment Intersection Graphs
• Triangles, 4-Cycles and Parameterized (In-)Tractability
• Stability preserving transformations of graphs
• Augmenting graphs for independent sets
• The independence number of graphs with large odd girth

Cited In (12)

• Parameterized complexity of the weighted independent set problem beyond graphs of bounded clique number
• Collaborating with Hans: Some Remaining Wonderments
• Parameterized complexity of finding subgraphs with hereditary properties on hereditary graph classes
• Title not available (Why is that?)
• Fixed cardinality stable sets
• Parameterized algorithms for Max Colorable Induced Subgraph problem on perfect graphs
• Parameterized inapproximability of independent set in \(H\)-free graphs
• On easy and hard hereditary classes of graphs with respect to the independent set problem
• Getting linear time in graphs of bounded neighborhood diversity
• Parameterized complexity of finding subgraphs with hereditary properties.
• On generalizations of the shadow independent set problem
• Parameterized complexity of the maximum independent set problem and the speed of hereditary properties

This page was built for publication: Parameterized algorithms for the independent set problem in some hereditary graph classes

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