A sufficient condition to extend polynomial results for the maximum independent set problem
From MaRDI portal
Publication:344869
DOI10.1016/j.dam.2015.10.023zbMath1350.05123OpenAlexW2189653983MaRDI QIDQ344869
Publication date: 24 November 2016
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.dam.2015.10.023
Structural characterization of families of graphs (05C75) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)
Related Items (3)
New results on independent sets in extensions of \(2K_2\)-free graphs ⋮ Independence number and the number of maximum independent sets in pseudofractal scale-free web and Sierpiński gasket ⋮ Algorithm to find a maximum 2-packing set in a cactus
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Maximum regular induced subgraphs in \(2P_3\)-free graphs
- On rigid circuit graphs
- Maximum independent sets in subclasses of \(P_{5}\)-free graphs
- On diameters and radii of bridged graphs
- On maximal independent sets of vertices in claw-free graphs
- Algorithme de recherche d'un stable de cardinalité maximum dans un graphe sans étoilé
- Some simplified NP-complete graph problems
- On easy and hard hereditary classes of graphs with respect to the independent set problem
- Independent sets in extensions of 2\(K_{2}\)-free graphs
- Sparse regular induced subgraphs in \(2P_3\)-free graphs
- Maximum weight independent sets in (\(P_6\), co-banner)-free graphs
- An \(\mathcal{O}(m\log n)\) algorithm for the weighted stable set problem in claw-free graphs with \(\alpha ({G}) \leq 3\)
- Incidence matrices and interval graphs
- Triangulated graphs and the elimination process
- A Linear Recognition Algorithm for Cographs
- A New Algorithm for Generating All the Maximal Independent Sets
- The Rectilinear Steiner Tree Problem is $NP$-Complete
- Graph Classes: A Survey
- A REVISION OF MINTY'S ALGORITHM FOR FINDING A MAXIMUM WEIGHT STABLE SET OF A CLAW-FREE GRAPH
- Polynomial algorithm for finding the largest independent sets in graphs without forks
- Independent Set in P5-Free Graphs in Polynomial Time
- Solving the Weighted Stable Set Problem in Claw-Free Graphs via Decomposition
- Independent Sets of Maximum Weight in Apple-Free Graphs
- Independent Sets of Maximum Weight in Apple-Free Graphs
- A polynomial algorithm to find an independent set of maximum weight in a fork-free graph
This page was built for publication: A sufficient condition to extend polynomial results for the maximum independent set problem
