Maximum weight archipelago subgraph problem View Full Text


Ontology type: schema:ScholarlyArticle     


Article Info

DATE

2014-06

AUTHORS

Peter L. Hammer, Péter Majlender, Bruno Simeone, Béla Vizvári

ABSTRACT

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. More... »

PAGES

253-262

References to SciGraph publications

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/s10479-013-1518-x

DOI

http://dx.doi.org/10.1007/s10479-013-1518-x

DIMENSIONS

https://app.dimensions.ai/details/publication/pub.1000662624


Indexing Status Check whether this publication has been indexed by Scopus and Web Of Science using the SN Indexing Status Tool
Incoming Citations Browse incoming citations for this publication using opencitations.net

JSON-LD is the canonical representation for SciGraph data.

TIP: You can open this SciGraph record using an external JSON-LD service: JSON-LD Playground Google SDTT

[
  {
    "@context": "https://springernature.github.io/scigraph/jsonld/sgcontext.json", 
    "about": [
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0802", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Computation Theory and Mathematics", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/08", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Information and Computing Sciences", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Rutgers University", 
          "id": "https://www.grid.ac/institutes/grid.430387.b", 
          "name": [
            "RUTCOR, Rutgers University, Piscataway, NJ, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Hammer", 
        "givenName": "Peter L.", 
        "id": "sg:person.015740461177.00", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015740461177.00"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Stockholm University", 
          "id": "https://www.grid.ac/institutes/grid.10548.38", 
          "name": [
            "Department of Computer and Systems Sciences, Stockholm University, Stockholm, Sweden"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Majlender", 
        "givenName": "P\u00e9ter", 
        "id": "sg:person.07737720621.67", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07737720621.67"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "name": [
            "La Sapienzia University, Rome, Italy"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Simeone", 
        "givenName": "Bruno", 
        "id": "sg:person.012600006066.78", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012600006066.78"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Eastern Mediterranean University", 
          "id": "https://www.grid.ac/institutes/grid.461270.6", 
          "name": [
            "Department of Industrial Engineering, Eastern Mediterranean University, Famagusta, Cyprus"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Vizv\u00e1ri", 
        "givenName": "B\u00e9la", 
        "id": "sg:person.014455010473.32", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014455010473.32"
        ], 
        "type": "Person"
      }
    ], 
    "citation": [
      {
        "id": "sg:pub.10.1007/bf01096457", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1000499730", 
          "https://doi.org/10.1007/bf01096457"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bf01096457", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1000499730", 
          "https://doi.org/10.1007/bf01096457"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/0020-0190(78)90030-3", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1006177335"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1002/j.1538-7305.1957.tb01515.x", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1025892743"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1287/mnsc.25.3.264", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1064719172"
        ], 
        "type": "CreativeWork"
      }
    ], 
    "datePublished": "2014-06", 
    "datePublishedReg": "2014-06-01", 
    "description": "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.", 
    "genre": "research_article", 
    "id": "sg:pub.10.1007/s10479-013-1518-x", 
    "inLanguage": [
      "en"
    ], 
    "isAccessibleForFree": false, 
    "isPartOf": [
      {
        "id": "sg:journal.1048429", 
        "issn": [
          "0254-5330", 
          "1572-9338"
        ], 
        "name": "Annals of Operations Research", 
        "type": "Periodical"
      }, 
      {
        "issueNumber": "1", 
        "type": "PublicationIssue"
      }, 
      {
        "type": "PublicationVolume", 
        "volumeNumber": "217"
      }
    ], 
    "name": "Maximum weight archipelago subgraph problem", 
    "pagination": "253-262", 
    "productId": [
      {
        "name": "readcube_id", 
        "type": "PropertyValue", 
        "value": [
          "0327f3d4ce328c2d4b1d17411e77e76af03d7b41489025cdfaeb45cb3743a919"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/s10479-013-1518-x"
        ]
      }, 
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1000662624"
        ]
      }
    ], 
    "sameAs": [
      "https://doi.org/10.1007/s10479-013-1518-x", 
      "https://app.dimensions.ai/details/publication/pub.1000662624"
    ], 
    "sdDataset": "articles", 
    "sdDatePublished": "2019-04-10T13:15", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-uberresearch-data-dimensions-target-20181106-alternative/cleanup/v134/2549eaecd7973599484d7c17b260dba0a4ecb94b/merge/v9/a6c9fde33151104705d4d7ff012ea9563521a3ce/jats-lookup/v90/0000000001_0000000264/records_8659_00000509.jsonl", 
    "type": "ScholarlyArticle", 
    "url": "http://link.springer.com/10.1007%2Fs10479-013-1518-x"
  }
]
 

Download the RDF metadata as:  json-ld nt turtle xml License info

HOW TO GET THIS DATA PROGRAMMATICALLY:

JSON-LD is a popular format for linked data which is fully compatible with JSON.

curl -H 'Accept: application/ld+json' 'https://scigraph.springernature.com/pub.10.1007/s10479-013-1518-x'

N-Triples is a line-based linked data format ideal for batch operations.

curl -H 'Accept: application/n-triples' 'https://scigraph.springernature.com/pub.10.1007/s10479-013-1518-x'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/s10479-013-1518-x'

RDF/XML is a standard XML format for linked data.

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/s10479-013-1518-x'


 

This table displays all metadata directly associated to this object as RDF triples.

103 TRIPLES      21 PREDICATES      31 URIs      19 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/s10479-013-1518-x schema:about anzsrc-for:08
2 anzsrc-for:0802
3 schema:author N2dd45d4f599e4f459ec5445e2365ecef
4 schema:citation sg:pub.10.1007/bf01096457
5 https://doi.org/10.1002/j.1538-7305.1957.tb01515.x
6 https://doi.org/10.1016/0020-0190(78)90030-3
7 https://doi.org/10.1287/mnsc.25.3.264
8 schema:datePublished 2014-06
9 schema:datePublishedReg 2014-06-01
10 schema:description 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.
11 schema:genre research_article
12 schema:inLanguage en
13 schema:isAccessibleForFree false
14 schema:isPartOf N122d5ec1594043a0bd27247b83e6cf3f
15 Nd34bc742e781417d806abf2e6715520f
16 sg:journal.1048429
17 schema:name Maximum weight archipelago subgraph problem
18 schema:pagination 253-262
19 schema:productId N53f725884f2a4331ba362027517c6be3
20 N86e10aa7625941ec9a72e36a11d611e2
21 Nbb28af56f8f544668358a8ea42ccc59c
22 schema:sameAs https://app.dimensions.ai/details/publication/pub.1000662624
23 https://doi.org/10.1007/s10479-013-1518-x
24 schema:sdDatePublished 2019-04-10T13:15
25 schema:sdLicense https://scigraph.springernature.com/explorer/license/
26 schema:sdPublisher Nc4b1fbde57e741608d4cb53e72dadaff
27 schema:url http://link.springer.com/10.1007%2Fs10479-013-1518-x
28 sgo:license sg:explorer/license/
29 sgo:sdDataset articles
30 rdf:type schema:ScholarlyArticle
31 N122d5ec1594043a0bd27247b83e6cf3f schema:issueNumber 1
32 rdf:type schema:PublicationIssue
33 N2dd45d4f599e4f459ec5445e2365ecef rdf:first sg:person.015740461177.00
34 rdf:rest N4ce74f68aa3940748acab491132e10c5
35 N4ce74f68aa3940748acab491132e10c5 rdf:first sg:person.07737720621.67
36 rdf:rest Nc20eba18575347ef9264514b1af9eff9
37 N4e73f211f6054094b394505be8457682 schema:name La Sapienzia University, Rome, Italy
38 rdf:type schema:Organization
39 N53f725884f2a4331ba362027517c6be3 schema:name doi
40 schema:value 10.1007/s10479-013-1518-x
41 rdf:type schema:PropertyValue
42 N6167ca828b3b48908ccb0eaae3585179 rdf:first sg:person.014455010473.32
43 rdf:rest rdf:nil
44 N86e10aa7625941ec9a72e36a11d611e2 schema:name readcube_id
45 schema:value 0327f3d4ce328c2d4b1d17411e77e76af03d7b41489025cdfaeb45cb3743a919
46 rdf:type schema:PropertyValue
47 Nbb28af56f8f544668358a8ea42ccc59c schema:name dimensions_id
48 schema:value pub.1000662624
49 rdf:type schema:PropertyValue
50 Nc20eba18575347ef9264514b1af9eff9 rdf:first sg:person.012600006066.78
51 rdf:rest N6167ca828b3b48908ccb0eaae3585179
52 Nc4b1fbde57e741608d4cb53e72dadaff schema:name Springer Nature - SN SciGraph project
53 rdf:type schema:Organization
54 Nd34bc742e781417d806abf2e6715520f schema:volumeNumber 217
55 rdf:type schema:PublicationVolume
56 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
57 schema:name Information and Computing Sciences
58 rdf:type schema:DefinedTerm
59 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
60 schema:name Computation Theory and Mathematics
61 rdf:type schema:DefinedTerm
62 sg:journal.1048429 schema:issn 0254-5330
63 1572-9338
64 schema:name Annals of Operations Research
65 rdf:type schema:Periodical
66 sg:person.012600006066.78 schema:affiliation N4e73f211f6054094b394505be8457682
67 schema:familyName Simeone
68 schema:givenName Bruno
69 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012600006066.78
70 rdf:type schema:Person
71 sg:person.014455010473.32 schema:affiliation https://www.grid.ac/institutes/grid.461270.6
72 schema:familyName Vizvári
73 schema:givenName Béla
74 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014455010473.32
75 rdf:type schema:Person
76 sg:person.015740461177.00 schema:affiliation https://www.grid.ac/institutes/grid.430387.b
77 schema:familyName Hammer
78 schema:givenName Peter L.
79 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015740461177.00
80 rdf:type schema:Person
81 sg:person.07737720621.67 schema:affiliation https://www.grid.ac/institutes/grid.10548.38
82 schema:familyName Majlender
83 schema:givenName Péter
84 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07737720621.67
85 rdf:type schema:Person
86 sg:pub.10.1007/bf01096457 schema:sameAs https://app.dimensions.ai/details/publication/pub.1000499730
87 https://doi.org/10.1007/bf01096457
88 rdf:type schema:CreativeWork
89 https://doi.org/10.1002/j.1538-7305.1957.tb01515.x schema:sameAs https://app.dimensions.ai/details/publication/pub.1025892743
90 rdf:type schema:CreativeWork
91 https://doi.org/10.1016/0020-0190(78)90030-3 schema:sameAs https://app.dimensions.ai/details/publication/pub.1006177335
92 rdf:type schema:CreativeWork
93 https://doi.org/10.1287/mnsc.25.3.264 schema:sameAs https://app.dimensions.ai/details/publication/pub.1064719172
94 rdf:type schema:CreativeWork
95 https://www.grid.ac/institutes/grid.10548.38 schema:alternateName Stockholm University
96 schema:name Department of Computer and Systems Sciences, Stockholm University, Stockholm, Sweden
97 rdf:type schema:Organization
98 https://www.grid.ac/institutes/grid.430387.b schema:alternateName Rutgers University
99 schema:name RUTCOR, Rutgers University, Piscataway, NJ, USA
100 rdf:type schema:Organization
101 https://www.grid.ac/institutes/grid.461270.6 schema:alternateName Eastern Mediterranean University
102 schema:name Department of Industrial Engineering, Eastern Mediterranean University, Famagusta, Cyprus
103 rdf:type schema:Organization
 




Preview window. Press ESC to close (or click here)


...