Change search
ReferencesLink to record
Permanent link

Direct link
Maximum weight archipelago subgraph problem
Stockholm University, Faculty of Social Sciences, Department of Computer and Systems Sciences.
2014 (English)In: Annals of Operations Research, ISSN 0254-5330, E-ISSN 1572-9338, Vol. 217, no 1, 253-262 p.Article in journal (Refereed) Published
Abstract [en]

This paper is devoted to a new problem of combinatorial optimization. The problem is called Maximum Weight Archipelago Subgraph Problem (MWASP). Archipelago is a signed graph such that the negative edges connect the components of the graph of the positive edges. The new problem is to find a subset of edges in a weighted signed graph such that (i) if the edges of the subset are deleted from the graph then the remaining graph is an archipelago; and (ii) the subset has minimal total weight among the subsets having property (i). The problem is NP-complete, however a polynomial algorithm is provided to obtain the maximal weight of an edge what is still necessary to delete. The problem MWAP is used to analyze the relation of the blue chips of the Dow Jones Index.

Place, publisher, year, edition, pages
2014. Vol. 217, no 1, 253-262 p.
Keyword [en]
Set covering problem, Maximum weight archipelago subgraph problem, Dow Jones index
National Category
Information Systems
URN: urn:nbn:se:su:diva-106086DOI: 10.1007/s10479-013-1518-xISI: 000337184500011OAI: diva2:735445


Available from: 2014-07-28 Created: 2014-07-21 Last updated: 2014-07-28Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full text
By organisation
Department of Computer and Systems Sciences
In the same journal
Annals of Operations Research
Information Systems

Search outside of DiVA

GoogleGoogle Scholar
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Altmetric score

Total: 27 hits
ReferencesLink to record
Permanent link

Direct link