On solving a non-convex quadratic programming problem involving resistance distances in graphs

Dipti Dubey () and S. K. Neogy ()
Additional contact information
Dipti Dubey: Indian Statistical Institute
S. K. Neogy: Indian Statistical Institute

Annals of Operations Research, 2020, vol. 287, issue 2, No 5, 643-651

Abstract: Abstract Quadratic programming problems involving distance matrix (D) that arises in trees are considered in the literature by Dankelmann (Discrete Math 312:12–20, 2012), Bapat and Neogy (Ann Oper Res 243:365–373, 2016). In this paper, we consider the question of solving the quadratic programming problem of finding maximum of $$x^{T}Rx$$xTRx subject to x being a nonnegative vector with sum 1 and show that for the class of simple graphs with resistance distance matrix (R) which are not necessarily a tree, this problem can be reformulated as a strictly convex quadratic programming problem. An application to symmetric bimatrix game is also presented.

Keywords: Resistance distance; Laplacian matrix; Non-convex quadratic programming; Polynomial time algorithm; Symmetric bimatrix game; 90C33 (search for similar items in EconPapers)
Date: 2020
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10479-018-3018-5 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:annopr:v:287:y:2020:i:2:d:10.1007_s10479-018-3018-5

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10479

DOI: 10.1007/s10479-018-3018-5

Access Statistics for this article

Annals of Operations Research is currently edited by Endre Boros

More articles in Annals of Operations Research from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().