A sufficient condition to extend polynomial results for the maximum independent set problem
type: Item
instance of: scholarly article
title: A sufficient condition to extend polynomial results for the maximum independent set problem
zbMATH Open document ID: 1350.05123
author: Raffaele Mosca
published in: Discrete Applied Mathematics
publication date: 2016-11-24T00:00:00Z
Mathematics Subject Classification ID: 05C69
Mathematics Subject Classification ID: 05C75
Mathematics Subject Classification ID: 68Q17
zbMATH DE Number: 6656025
zbMATH Keywords: maximum independent set problem
zbMATH Keywords: polynomial algorithms
MaRDI profile type: MaRDI publication profile
full work available at URL: j.dam.2015.10.023
OpenAlex ID: W2189653983
cites work: Polynomial algorithm for finding the largest independent sets in graphs without forks
cites work: On easy and hard hereditary classes of graphs with respect to the independent set problem
cites work: Independent Sets of Maximum Weight in Apple-Free Graphs
cites work: Graph Classes: A Survey
cites work: A Linear Recognition Algorithm for Cographs
cites work: On rigid circuit graphs
cites work: Solving the Weighted Stable Set Problem in Claw-Free Graphs via Decomposition
cites work: On diameters and radii of bridged graphs
cites work: Q4093489
cites work: Independence and irredundance in \(k\)-regular graphs
cites work: Incidence matrices and interval graphs
cites work: The Rectilinear Steiner Tree Problem is $NP$-Complete
cites work: Q4198056
cites work: Some simplified NP-complete graph problems
cites work: Q3216686
cites work: Independent Set in P5-Free Graphs in Polynomial Time
cites work: A polynomial algorithm to find an independent set of maximum weight in a fork-free graph
cites work: Maximum independent sets in subclasses of \(P_{5}\)-free graphs
cites work: Independent sets in extensions of 2\(K_{2}\)-free graphs
cites work: Maximum regular induced subgraphs in \(2P_3\)-free graphs
cites work: Sparse regular induced subgraphs in \(2P_3\)-free graphs
cites work: On maximal independent sets of vertices in claw-free graphs
cites work: Maximum weight independent sets in (\(P_6\), co-banner)-free graphs
cites work: A REVISION OF MINTY'S ALGORITHM FOR FINDING A MAXIMUM WEIGHT STABLE SET OF A CLAW-FREE GRAPH
cites work: An \(\mathcal{O}(m\log n)\) algorithm for the weighted stable set problem in claw-free graphs with \(\alpha ({G}) \leq 3\)
cites work: Q4770411
cites work: Q4871056
cites work: Triangulated graphs and the elimination process
cites work: Algorithme de recherche d'un stable de cardinalité maximum dans un graphe sans étoilé
cites work: A New Algorithm for Generating All the Maximal Independent Sets
DOI: 10.1016/J.DAM.2015.10.023
Recommended article: On the maximal independence polynomial of certain graph configurations
Recommended article: A generalization of maximal independent sets
Recommended article: On the maximum independent set problem in graphs of bounded maximum degree
Recommended article: On the maximum number of maximum independent sets
Recommended article: The \textsc{max quasi-independent set} problem
Recommended article: Q5717953
Recommended article: Constraints on the number of maximal independent sets in graphs
Recommended article: The generalized independent set problem: polyhedral analysis and solution approaches
Recommended article: Q5263782
Recommended article: Extending the MAX algorithm for maximum independent set
description: scientific article; zbMATH DE number 6656025