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.05075OpenAlexW2301532929MaRDI 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 problemscontinuous formulations of discrete problemsindependent domination number in graphsLovasz thetaweighted independence number in graphswell covered graphs

Mathematics Subject Classification ID

Convex programming (90C25) Quadratic programming (90C20) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (1)

On independent cliques and linear complementarity problems

Uses Software

• SDPT3
• DIMACS

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Solving semidefinite-quadratic-linear programs using SDPT3
• An LPCC approach to nonconvex quadratic programs
• On the variational equilibrium as a refinement of the generalized Nash equilibrium
• On linear programs with linear complementarity constraints
• The combinatorics of pivoting for the maximum weight clique.
• Semidefinite programming relaxations for graph coloring and maximal clique problems
• Relaxations of vertex packing
• NP-completeness of the linear complementarity problem
• On maximal independent sets of vertices in claw-free graphs
• Some fundamental properties of successive convex relaxation methods on LCP and related problems
• Non-cooperative games
• A Complementary Pivoting Approach to the Maximum Weight Clique Problem
• Integer Programming
• The Operator $\Psi$ for the Chromatic Number of a Graph
• Cones of Matrices and Set-Functions and 0–1 Optimization
• WELL-COVERED GRAPHS: A SURVEY
• Continuous Characterizations of the Maximum Clique Problem
• SDPT3 — A Matlab software package for semidefinite programming, Version 1.3
• Some news about the independence number of a graph
• Semidefinite Programming
• On Dominating Sets and Independent Sets of Graphs
• Maxima for Graphs and a New Proof of a Theorem of Turán

This page was built for publication: A linear complementarity based characterization of the weighted independence number and the independent domination number in graphs