A sufficient condition to extend polynomial results for the maximum independent set problem

DOI10.1016/J.DAM.2015.10.023MaRDI QIDQ344869zbMATH OpenOpenAlexFDO

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

polynomial algorithms maximum independent set problem

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)

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

Cites work

scientific article; zbMATH DE number 3882470 (Why is no real title available?)
scientific article; zbMATH DE number 3513839 (Why is no real title available?)
scientific article; zbMATH DE number 3639144 (Why is no real title available?)
scientific article; zbMATH DE number 3445275 (Why is no real title available?)
scientific article; zbMATH DE number 861332 (Why is no real title available?)
A Linear Recognition Algorithm for Cographs
A New Algorithm for Generating All the Maximal Independent Sets
A REVISION OF MINTY'S ALGORITHM FOR FINDING A MAXIMUM WEIGHT STABLE SET OF A CLAW-FREE GRAPH
A polynomial algorithm to find an independent set of maximum weight in a fork-free graph
Algorithme de recherche d'un stable de cardinalité maximum dans un graphe sans étoilé
An $\mathcal{O}(m\log n)$ algorithm for the weighted stable set problem in claw-free graphs with $\alpha ({G}) \leq 3$
Graph Classes: A Survey
Incidence matrices and interval graphs
Independence and irredundance in $k$-regular graphs
Independent Sets of Maximum Weight in Apple-Free Graphs
Independent set in $P_5$-free graphs in polynomial time
Independent sets in extensions of 2$K_{2}$-free graphs
Independent sets of maximum weight in apple-free graphs
Maximum independent sets in subclasses of $P_{5}$-free graphs
Maximum regular induced subgraphs in $2P_3$-free graphs
Maximum weight independent sets in ($P_6$, co-banner)-free graphs
On diameters and radii of bridged graphs
On easy and hard hereditary classes of graphs with respect to the independent set problem
On maximal independent sets of vertices in claw-free graphs
On rigid circuit graphs
Polynomial algorithm for finding the largest independent sets in graphs without forks
Solving the weighted stable set problem in claw-free graphs via decomposition
Some simplified NP-complete graph problems
Sparse regular induced subgraphs in $2P_3$-free graphs
The Rectilinear Steiner Tree Problem is $NP$-Complete
Triangulated graphs and the elimination process

Cited in

(6)

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
Independent sets in extensions of 2$K_{2}$-free graphs
New properties of maximum independent set problem solution truncation rules or redundant branches
New results on independent sets in extensions of $2K_2$-free graphs
Finding Critical Independent Sets and Critical Vertex Subsets are Polynomial Problems

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)