Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
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
Identifiers
URN: urn:nbn:se:su:diva-106086DOI: 10.1007/s10479-013-1518-xISI: 000337184500011OAI: oai:DiVA.org:su-106086DiVA: diva2:735445
Note

AuthorCount:4;

Available from: 2014-07-28 Created: 2014-07-21 Last updated: 2017-12-05Bibliographically 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

doi
urn-nbn

Altmetric score

doi
urn-nbn
Total: 31 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf