A generalization of the Hoffman-Lovász upper bound on the independence number of a regular graph
From MaRDI portal
Publication:1265892
DOI10.1023/A:1018965309522zbMath0908.90260MaRDI QIDQ1265892
Carlos J. Luz, Domingos Moreira Cardoso
Publication date: 27 September 1998
Published in: Annals of Operations Research (Search for Journal in Brave)
quadratic programmingcombinatorial optimizationgraph theoryindependence numberpolynomial-time algorithmmaximum independent set
Programming involving graphs or networks (90C35) Abstract computational complexity for mathematical programming problems (90C60) Combinatorial optimization (90C27)
Related Items (9)
Approximating the maximum size of a \(k\)-regular induced subgraph by an upper bound on the co-\(k\)-plex number ⋮ On hereditary properties of the class of graphs with convex quadratic stability number ⋮ A quadratic programming approach to the determination of an upper bound on the weighted stability number ⋮ Improving an upper bound on the stability number of a graph ⋮ A characterization of the weighted version of McEliece–Rodemich–Rumsey–Schrijver number based on convex quadratic programming ⋮ A simplex like approach based on star sets for recognizing convex-\(QP\) adverse graphs ⋮ A characterization of the weighted Lovász number based on convex quadratic programming ⋮ A survey on graphs with convex quadratic stability number ⋮ New results for recognizing convex-QP adverse graphs
This page was built for publication: A generalization of the Hoffman-Lovász upper bound on the independence number of a regular graph
