An upper bound on the independence number of a graph computable in polynomial-time
From MaRDI portal
Publication:1919180
DOI10.1016/0167-6377(95)00042-9zbMath0855.90134OpenAlexW2052426325WikidataQ127363278 ScholiaQ127363278MaRDI QIDQ1919180
Publication date: 11 February 1997
Published in: Operations Research Letters (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0167-6377(95)00042-9
Programming involving graphs or networks (90C35) Abstract computational complexity for mathematical programming problems (90C60) Quadratic programming (90C20) Combinatorial optimization (90C27)
Related Items (14)
A heuristic for the stability number of a graph based on convex quadratic programming and tabu search ⋮ A characterization of Delsarte's linear programming bound as a ratio bound ⋮ Improving an upper bound on the size of \(k\)-regular induced subgraphs ⋮ Maximum \(k\)-regular induced subgraphs ⋮ 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 ⋮ The \(k\)-regular induced subgraph problem ⋮ 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 ⋮ Dual Hoffman Bounds for the Stability and Chromatic Numbers Based on Semidefinite Programming
Cites Work
This page was built for publication: An upper bound on the independence number of a graph computable in polynomial-time
