An upper bound on the independence number of a graph computable in polynomial-time
type: Item
instance of: scholarly article
title: An upper bound on the independence number of a graph computable in polynomial-time
zbMATH Open document ID: 0855.90134
DOI: 10.1016/0167-6377(95)00042-9
author: Carlos J. Luz
published in: Operations Research Letters
publication date: 1997-02-11T00:00:00Z
Mathematics Subject Classification ID: 90C35
Mathematics Subject Classification ID: 90C60
Mathematics Subject Classification ID: 90C27
Mathematics Subject Classification ID: 90C20
zbMATH DE Number: 912525
zbMATH Keywords: maximum independent set
zbMATH Keywords: upper bound
zbMATH Keywords: independence number of an undirected graph
zbMATH Keywords: Lagrangian duality
MaRDI profile type: Publication
full work available at URL: 0167-6377(95)00042-9
OpenAlex ID: W2052426325
cites work: On the Shannon capacity of a graph
cites work: Matching theory
cites work: State Constraints in Convex Control Problems of Bolza
Wikidata QID: Q127363278
Recommended article: Upper bounds for the independence polynomial of graphs at \(-1\)
Recommended article: Q3139522
Recommended article: THE UPPER AND LOWER INDEPENDENCE NUMBER OF GRAPHS
Recommended article: A lower bound on the independence number of a graph
Recommended article: An upper bound for the number of maximal independent sets in a graph
Recommended article: A new lower bound on the independence number of graphs
Recommended article: An improved lower bound on the independence number of a graph
Recommended article: Q4374002
Recommended article: A probabilistic lower bound on the independence number of graphs
Recommended article: The Complexity of Finding Paths in Graphs with Bounded Independence Number
description: scientific article; zbMATH DE number 912525