A linear complementarity based characterization of the weighted independence number and the independent domination number in graphs

DOI10.1016/j.dam.2018.02.022zbMath1387.05184arXiv1603.05075MaRDI QIDQ1752600

Ankur A. Kulkarni, Parthe Pandit

Publication date: 24 May 2018

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1603.05075

zbMATH Keywords

linear complementarity problems; continuous formulations of discrete problems; independent domination number in graphs; Lovasz theta; weighted independence number in graphs; well covered graphs

Mathematics Subject Classification ID

90C25: Convex programming

90C20: Quadratic programming

05C70: Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)

05C69: Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)

Uses Software

• SDPT3
• DIMACS