Fully Dynamically Maintaining Minimal Integral Separator for Threshold and Difference Graphs View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2016

AUTHORS

Tiziana Calamoneri , Angelo Monti , Rossella Petreschi

ABSTRACT

This paper deals with the well known classes of threshold and difference graphs, both characterized by separators, i.e. node weight functions and thresholds. We show how to maintain minimum the value of the separator when the input (threshold or difference) graph is fully dynamic, i.e. edges/nodes are inserted/removed. Moreover, exploiting the data structure used for maintaining the minimality of the separator, we handle the operations of disjoint union and join of two threshold graphs. More... »

PAGES

313-324

Book

TITLE

WALCOM: Algorithms and Computation

ISBN

978-3-319-30138-9
978-3-319-30139-6

Author Affiliations

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-319-30139-6_25

DOI

http://dx.doi.org/10.1007/978-3-319-30139-6_25

DIMENSIONS

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


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/0806", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Information Systems", 
        "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": "Sapienza University of Rome", 
          "id": "https://www.grid.ac/institutes/grid.7841.a", 
          "name": [
            "Computer Science Department, \u201cSapienza\u201d University of Rome"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Calamoneri", 
        "givenName": "Tiziana", 
        "id": "sg:person.013577775161.22", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013577775161.22"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Sapienza University of Rome", 
          "id": "https://www.grid.ac/institutes/grid.7841.a", 
          "name": [
            "Computer Science Department, \u201cSapienza\u201d University of Rome"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Monti", 
        "givenName": "Angelo", 
        "id": "sg:person.013471123531.02", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013471123531.02"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Sapienza University of Rome", 
          "id": "https://www.grid.ac/institutes/grid.7841.a", 
          "name": [
            "Computer Science Department, \u201cSapienza\u201d University of Rome"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Petreschi", 
        "givenName": "Rossella", 
        "id": "sg:person.011402427702.78", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011402427702.78"
        ], 
        "type": "Person"
      }
    ], 
    "citation": [
      {
        "id": "https://doi.org/10.1016/s0167-5060(08)70749-0", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1015050349"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/0012-365x(82)90166-2", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1029539850"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1002/jgt.3190090207", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1030236237"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/j.tcs.2008.07.020", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1043949492"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/s0167-5060(08)70731-3", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1046754752"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/s0166-218x(03)00448-7", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1051502699"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/s0166-218x(03)00448-7", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1051502699"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1137/0206008", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1062841347"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1137/0603036", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1062848761"
        ], 
        "type": "CreativeWork"
      }
    ], 
    "datePublished": "2016", 
    "datePublishedReg": "2016-01-01", 
    "description": "This paper deals with the well known classes of threshold and difference graphs, both characterized by separators, i.e. node weight functions and thresholds. We show how to maintain minimum the value of the separator when the input (threshold or difference) graph is fully dynamic, i.e. edges/nodes are inserted/removed. Moreover, exploiting the data structure used for maintaining the minimality of the separator, we handle the operations of disjoint union and join of two threshold graphs.", 
    "editor": [
      {
        "familyName": "Kaykobad", 
        "givenName": "Mohammad", 
        "type": "Person"
      }, 
      {
        "familyName": "Petreschi", 
        "givenName": "Rossella", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-319-30139-6_25", 
    "inLanguage": [
      "en"
    ], 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-319-30138-9", 
        "978-3-319-30139-6"
      ], 
      "name": "WALCOM: Algorithms and Computation", 
      "type": "Book"
    }, 
    "name": "Fully Dynamically Maintaining Minimal Integral Separator for Threshold and Difference Graphs", 
    "pagination": "313-324", 
    "productId": [
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-319-30139-6_25"
        ]
      }, 
      {
        "name": "readcube_id", 
        "type": "PropertyValue", 
        "value": [
          "a7178e1e3fe56111b0990489defb5c97c9eb980e5ac8bc733e9233d93e749066"
        ]
      }, 
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1035076720"
        ]
      }
    ], 
    "publisher": {
      "location": "Cham", 
      "name": "Springer International Publishing", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-319-30139-6_25", 
      "https://app.dimensions.ai/details/publication/pub.1035076720"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2019-04-15T21:03", 
    "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_8690_00000265.jsonl", 
    "type": "Chapter", 
    "url": "http://link.springer.com/10.1007/978-3-319-30139-6_25"
  }
]
 

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/978-3-319-30139-6_25'

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/978-3-319-30139-6_25'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-319-30139-6_25'

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

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/978-3-319-30139-6_25'


 

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

108 TRIPLES      23 PREDICATES      35 URIs      20 LITERALS      8 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-319-30139-6_25 schema:about anzsrc-for:08
2 anzsrc-for:0806
3 schema:author N3c240bdace8743f1866d119f57f83070
4 schema:citation https://doi.org/10.1002/jgt.3190090207
5 https://doi.org/10.1016/0012-365x(82)90166-2
6 https://doi.org/10.1016/j.tcs.2008.07.020
7 https://doi.org/10.1016/s0166-218x(03)00448-7
8 https://doi.org/10.1016/s0167-5060(08)70731-3
9 https://doi.org/10.1016/s0167-5060(08)70749-0
10 https://doi.org/10.1137/0206008
11 https://doi.org/10.1137/0603036
12 schema:datePublished 2016
13 schema:datePublishedReg 2016-01-01
14 schema:description This paper deals with the well known classes of threshold and difference graphs, both characterized by separators, i.e. node weight functions and thresholds. We show how to maintain minimum the value of the separator when the input (threshold or difference) graph is fully dynamic, i.e. edges/nodes are inserted/removed. Moreover, exploiting the data structure used for maintaining the minimality of the separator, we handle the operations of disjoint union and join of two threshold graphs.
15 schema:editor N902cb76225da4f4fb5942e887dd8020e
16 schema:genre chapter
17 schema:inLanguage en
18 schema:isAccessibleForFree false
19 schema:isPartOf Nc34c1469776b4c52b54abe86cd97729f
20 schema:name Fully Dynamically Maintaining Minimal Integral Separator for Threshold and Difference Graphs
21 schema:pagination 313-324
22 schema:productId Na98eff08f8e34777b3b3a112b43adce9
23 Nc2e5d777f40e44979b96714634cc72ec
24 Ndfda238d249f40d3aefd0b223dc8da36
25 schema:publisher N038daf02323a4ec3b2f31ee299fbf289
26 schema:sameAs https://app.dimensions.ai/details/publication/pub.1035076720
27 https://doi.org/10.1007/978-3-319-30139-6_25
28 schema:sdDatePublished 2019-04-15T21:03
29 schema:sdLicense https://scigraph.springernature.com/explorer/license/
30 schema:sdPublisher N6ac2e485922d4fac9c7ddb6db8a03e7d
31 schema:url http://link.springer.com/10.1007/978-3-319-30139-6_25
32 sgo:license sg:explorer/license/
33 sgo:sdDataset chapters
34 rdf:type schema:Chapter
35 N038daf02323a4ec3b2f31ee299fbf289 schema:location Cham
36 schema:name Springer International Publishing
37 rdf:type schema:Organisation
38 N15df3d84ca634ac0b6b5283e6d04bce7 rdf:first sg:person.011402427702.78
39 rdf:rest rdf:nil
40 N25eb1f5939f448a69a6f29c7a9b9879b schema:familyName Petreschi
41 schema:givenName Rossella
42 rdf:type schema:Person
43 N3c240bdace8743f1866d119f57f83070 rdf:first sg:person.013577775161.22
44 rdf:rest N7f2d59eaf75f4797bcf5565d116b5d59
45 N6ac2e485922d4fac9c7ddb6db8a03e7d schema:name Springer Nature - SN SciGraph project
46 rdf:type schema:Organization
47 N7f2d59eaf75f4797bcf5565d116b5d59 rdf:first sg:person.013471123531.02
48 rdf:rest N15df3d84ca634ac0b6b5283e6d04bce7
49 N902cb76225da4f4fb5942e887dd8020e rdf:first Nde62c2b4c8b84b148fdef19253a3fd58
50 rdf:rest Nbf84ef98335f4727bb3bccaf59c1a2df
51 Na98eff08f8e34777b3b3a112b43adce9 schema:name readcube_id
52 schema:value a7178e1e3fe56111b0990489defb5c97c9eb980e5ac8bc733e9233d93e749066
53 rdf:type schema:PropertyValue
54 Nbf84ef98335f4727bb3bccaf59c1a2df rdf:first N25eb1f5939f448a69a6f29c7a9b9879b
55 rdf:rest rdf:nil
56 Nc2e5d777f40e44979b96714634cc72ec schema:name dimensions_id
57 schema:value pub.1035076720
58 rdf:type schema:PropertyValue
59 Nc34c1469776b4c52b54abe86cd97729f schema:isbn 978-3-319-30138-9
60 978-3-319-30139-6
61 schema:name WALCOM: Algorithms and Computation
62 rdf:type schema:Book
63 Nde62c2b4c8b84b148fdef19253a3fd58 schema:familyName Kaykobad
64 schema:givenName Mohammad
65 rdf:type schema:Person
66 Ndfda238d249f40d3aefd0b223dc8da36 schema:name doi
67 schema:value 10.1007/978-3-319-30139-6_25
68 rdf:type schema:PropertyValue
69 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
70 schema:name Information and Computing Sciences
71 rdf:type schema:DefinedTerm
72 anzsrc-for:0806 schema:inDefinedTermSet anzsrc-for:
73 schema:name Information Systems
74 rdf:type schema:DefinedTerm
75 sg:person.011402427702.78 schema:affiliation https://www.grid.ac/institutes/grid.7841.a
76 schema:familyName Petreschi
77 schema:givenName Rossella
78 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011402427702.78
79 rdf:type schema:Person
80 sg:person.013471123531.02 schema:affiliation https://www.grid.ac/institutes/grid.7841.a
81 schema:familyName Monti
82 schema:givenName Angelo
83 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013471123531.02
84 rdf:type schema:Person
85 sg:person.013577775161.22 schema:affiliation https://www.grid.ac/institutes/grid.7841.a
86 schema:familyName Calamoneri
87 schema:givenName Tiziana
88 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013577775161.22
89 rdf:type schema:Person
90 https://doi.org/10.1002/jgt.3190090207 schema:sameAs https://app.dimensions.ai/details/publication/pub.1030236237
91 rdf:type schema:CreativeWork
92 https://doi.org/10.1016/0012-365x(82)90166-2 schema:sameAs https://app.dimensions.ai/details/publication/pub.1029539850
93 rdf:type schema:CreativeWork
94 https://doi.org/10.1016/j.tcs.2008.07.020 schema:sameAs https://app.dimensions.ai/details/publication/pub.1043949492
95 rdf:type schema:CreativeWork
96 https://doi.org/10.1016/s0166-218x(03)00448-7 schema:sameAs https://app.dimensions.ai/details/publication/pub.1051502699
97 rdf:type schema:CreativeWork
98 https://doi.org/10.1016/s0167-5060(08)70731-3 schema:sameAs https://app.dimensions.ai/details/publication/pub.1046754752
99 rdf:type schema:CreativeWork
100 https://doi.org/10.1016/s0167-5060(08)70749-0 schema:sameAs https://app.dimensions.ai/details/publication/pub.1015050349
101 rdf:type schema:CreativeWork
102 https://doi.org/10.1137/0206008 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062841347
103 rdf:type schema:CreativeWork
104 https://doi.org/10.1137/0603036 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062848761
105 rdf:type schema:CreativeWork
106 https://www.grid.ac/institutes/grid.7841.a schema:alternateName Sapienza University of Rome
107 schema:name Computer Science Department, “Sapienza” University of Rome
108 rdf:type schema:Organization
 




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


...