A sufficient condition to extend polynomial results for the maximum independent set problem
DOI10.1016/J.DAM.2015.10.023zbMATH Open1350.05123OpenAlexW2189653983MaRDI QIDQ344869FDOQ344869
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
Recommendations
- On the maximal independence polynomial of certain graph configurations
- A generalization of maximal independent sets
- On the maximum independent set problem in graphs of bounded maximum degree
- On the maximum number of maximum independent sets
- The \textsc{max quasi-independent set} problem
- scientific article; zbMATH DE number 2246590
- Constraints on the number of maximal independent sets in graphs
- The generalized independent set problem: polyhedral analysis and solution approaches
- scientific article; zbMATH DE number 6460018
- Extending the MAX algorithm for maximum independent set
Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Structural characterization of families of graphs (05C75)
Cites Work
- Title not available (Why is that?)
- Graph Classes: A Survey
- Algorithme de recherche d'un stable de cardinalité maximum dans un graphe sans étoilé
- 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
- Incidence matrices and interval graphs
- Title not available (Why is that?)
- A New Algorithm for Generating All the Maximal Independent Sets
- Independent Set in P5-Free Graphs in Polynomial Time
- Maximum regular induced subgraphs in \(2P_3\)-free graphs
- On rigid circuit graphs
- Some simplified NP-complete graph problems
- On maximal independent sets of vertices in claw-free graphs
- Triangulated graphs and the elimination process
- The Rectilinear Steiner Tree Problem is $NP$-Complete
- Title not available (Why is that?)
- On diameters and radii of bridged graphs
- Maximum weight independent sets in (\(P_6\), co-banner)-free graphs
- A Linear Recognition Algorithm for Cographs
- 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
- Polynomial algorithm for finding the largest independent sets in graphs without forks
- Maximum independent sets in subclasses of \(P_{5}\)-free graphs
- Title not available (Why is that?)
- An \(\mathcal{O}(m\log n)\) algorithm for the weighted stable set problem in claw-free graphs with \(\alpha ({G}) \leq 3\)
- Independence and irredundance in \(k\)-regular graphs
- A REVISION OF MINTY'S ALGORITHM FOR FINDING A MAXIMUM WEIGHT STABLE SET OF A CLAW-FREE GRAPH
- Title not available (Why is that?)
- Solving the Weighted Stable Set Problem in Claw-Free Graphs via Decomposition
- Independent Sets of Maximum Weight in Apple-Free Graphs
Cited In (6)
- Finding Critical Independent Sets and Critical Vertex Subsets are Polynomial Problems
- New properties of maximum independent set problem solution truncation rules or redundant branches
- Algorithm to find a maximum 2-packing set in a cactus
- New results on independent sets in extensions of \(2K_2\)-free graphs
- Independent sets in extensions of 2\(K_{2}\)-free graphs
- Independence number and the number of maximum independent sets in pseudofractal scale-free web and Sierpiński gasket
This page was built for publication: A sufficient condition to extend polynomial results for the maximum independent set problem
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q344869)
