Recognition of Unigraphs through Superposition of Graphs (Extended Abstract) View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2009

AUTHORS

Alessandro Borri , Tiziana Calamoneri , Rossella Petreschi

ABSTRACT

Unigraphs are graphs uniquely determined by their own degree sequence up to isomorphism. In this paper a structural description for unigraphs is introduced: vertex set is partitioned into three disjoint sets while edge set is divided into two different classes. This characterization allows us to design a linear time recognition algorithm that works recursively pruning the degree sequence of the graph. The algorithm detects two particular graphs whose superposition generates the given unigraph. More... »

PAGES

165-176

Book

TITLE

WALCOM: Algorithms and Computation

ISBN

978-3-642-00201-4
978-3-642-00202-1

Author Affiliations

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-642-00202-1_15

DOI

http://dx.doi.org/10.1007/978-3-642-00202-1_15

DIMENSIONS

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


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/0801", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Artificial Intelligence and Image Processing", 
        "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": [
            "Department of Computer Science, Univ. of Rome \u201cSapienza\u201d - Italy, via Salaria 113, 00198, Roma, Italy"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Borri", 
        "givenName": "Alessandro", 
        "id": "sg:person.012173062656.50", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012173062656.50"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Sapienza University of Rome", 
          "id": "https://www.grid.ac/institutes/grid.7841.a", 
          "name": [
            "Department of Computer Science, Univ. of Rome \u201cSapienza\u201d - Italy, via Salaria 113, 00198, Roma, Italy"
          ], 
          "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": [
            "Department of Computer Science, Univ. of Rome \u201cSapienza\u201d - Italy, via Salaria 113, 00198, Roma, Italy"
          ], 
          "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/0012-365x(84)90023-2", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1001514301"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/s0095-8956(76)80007-x", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1006901821"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1002/sapm1975544283", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1012144983"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "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/s0012-365x(99)00381-7", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1019371700"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/s0012-365x(96)00171-9", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1020072806"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/s0020-0190(00)00041-7", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1033464701"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/0012-365x(84)90026-8", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1038841355"
        ], 
        "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/j.dam.2006.03.036", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1048103103"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1137/0110037", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1062837838"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.2140/pjm.1975.56.143", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1069066208"
        ], 
        "type": "CreativeWork"
      }
    ], 
    "datePublished": "2009", 
    "datePublishedReg": "2009-01-01", 
    "description": "Unigraphs are graphs uniquely determined by their own degree sequence up to isomorphism. In this paper a structural description for unigraphs is introduced: vertex set is partitioned into three disjoint sets while edge set is divided into two different classes. This characterization allows us to design a linear time recognition algorithm that works recursively pruning the degree sequence of the graph. The algorithm detects two particular graphs whose superposition generates the given unigraph.", 
    "editor": [
      {
        "familyName": "Das", 
        "givenName": "Sandip", 
        "type": "Person"
      }, 
      {
        "familyName": "Uehara", 
        "givenName": "Ryuhei", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-642-00202-1_15", 
    "inLanguage": [
      "en"
    ], 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-642-00201-4", 
        "978-3-642-00202-1"
      ], 
      "name": "WALCOM: Algorithms and Computation", 
      "type": "Book"
    }, 
    "name": "Recognition of Unigraphs through Superposition of Graphs (Extended Abstract)", 
    "pagination": "165-176", 
    "productId": [
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-642-00202-1_15"
        ]
      }, 
      {
        "name": "readcube_id", 
        "type": "PropertyValue", 
        "value": [
          "0e90dff45197ef5672a77f1cefc009f990fbf901165ae9a60ba964484b410f1b"
        ]
      }, 
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1003057903"
        ]
      }
    ], 
    "publisher": {
      "location": "Berlin, Heidelberg", 
      "name": "Springer Berlin Heidelberg", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-642-00202-1_15", 
      "https://app.dimensions.ai/details/publication/pub.1003057903"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2019-04-16T06:12", 
    "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/0000000351_0000000351/records_43225_00000000.jsonl", 
    "type": "Chapter", 
    "url": "https://link.springer.com/10.1007%2F978-3-642-00202-1_15"
  }
]
 

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-642-00202-1_15'

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-642-00202-1_15'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-00202-1_15'

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-642-00202-1_15'


 

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

120 TRIPLES      23 PREDICATES      39 URIs      20 LITERALS      8 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-642-00202-1_15 schema:about anzsrc-for:08
2 anzsrc-for:0801
3 schema:author Nf96ffbeeb6fc43238ceebb80124da314
4 schema:citation https://doi.org/10.1002/sapm1975544283
5 https://doi.org/10.1016/0012-365x(84)90023-2
6 https://doi.org/10.1016/0012-365x(84)90026-8
7 https://doi.org/10.1016/j.dam.2006.03.036
8 https://doi.org/10.1016/s0012-365x(96)00171-9
9 https://doi.org/10.1016/s0012-365x(99)00381-7
10 https://doi.org/10.1016/s0020-0190(00)00041-7
11 https://doi.org/10.1016/s0095-8956(76)80007-x
12 https://doi.org/10.1016/s0167-5060(08)70731-3
13 https://doi.org/10.1016/s0167-5060(08)70749-0
14 https://doi.org/10.1137/0110037
15 https://doi.org/10.2140/pjm.1975.56.143
16 schema:datePublished 2009
17 schema:datePublishedReg 2009-01-01
18 schema:description Unigraphs are graphs uniquely determined by their own degree sequence up to isomorphism. In this paper a structural description for unigraphs is introduced: vertex set is partitioned into three disjoint sets while edge set is divided into two different classes. This characterization allows us to design a linear time recognition algorithm that works recursively pruning the degree sequence of the graph. The algorithm detects two particular graphs whose superposition generates the given unigraph.
19 schema:editor N4e981590895442cbbb016b1ba15b19c3
20 schema:genre chapter
21 schema:inLanguage en
22 schema:isAccessibleForFree false
23 schema:isPartOf N7e4f81ac38e94b3c970eec943e6360d8
24 schema:name Recognition of Unigraphs through Superposition of Graphs (Extended Abstract)
25 schema:pagination 165-176
26 schema:productId N981722b7066c4d0bae97848714c52d83
27 Nd8df538b86124d198950cebfb4916ac1
28 Nf22397d33b4f49e093c8b0952029a54c
29 schema:publisher N5471f4b8fe7444e4ad4959baf9ee6f56
30 schema:sameAs https://app.dimensions.ai/details/publication/pub.1003057903
31 https://doi.org/10.1007/978-3-642-00202-1_15
32 schema:sdDatePublished 2019-04-16T06:12
33 schema:sdLicense https://scigraph.springernature.com/explorer/license/
34 schema:sdPublisher N26f788caabb343029bdc57e9e4c91763
35 schema:url https://link.springer.com/10.1007%2F978-3-642-00202-1_15
36 sgo:license sg:explorer/license/
37 sgo:sdDataset chapters
38 rdf:type schema:Chapter
39 N1a83b283b0214e30bb53296270331011 rdf:first sg:person.011402427702.78
40 rdf:rest rdf:nil
41 N26f788caabb343029bdc57e9e4c91763 schema:name Springer Nature - SN SciGraph project
42 rdf:type schema:Organization
43 N4e981590895442cbbb016b1ba15b19c3 rdf:first Nd7022592a9fb463aa5e8aebef71c0066
44 rdf:rest Ne6f02641159843e996c5d8ee1ba7fb4b
45 N5471f4b8fe7444e4ad4959baf9ee6f56 schema:location Berlin, Heidelberg
46 schema:name Springer Berlin Heidelberg
47 rdf:type schema:Organisation
48 N7e4f81ac38e94b3c970eec943e6360d8 schema:isbn 978-3-642-00201-4
49 978-3-642-00202-1
50 schema:name WALCOM: Algorithms and Computation
51 rdf:type schema:Book
52 N981722b7066c4d0bae97848714c52d83 schema:name readcube_id
53 schema:value 0e90dff45197ef5672a77f1cefc009f990fbf901165ae9a60ba964484b410f1b
54 rdf:type schema:PropertyValue
55 Na6bc83ed68bc40308f157aeee868174a rdf:first sg:person.013577775161.22
56 rdf:rest N1a83b283b0214e30bb53296270331011
57 Naf0c40ec479d4e1ba7273ac7500c0e1e schema:familyName Uehara
58 schema:givenName Ryuhei
59 rdf:type schema:Person
60 Nd7022592a9fb463aa5e8aebef71c0066 schema:familyName Das
61 schema:givenName Sandip
62 rdf:type schema:Person
63 Nd8df538b86124d198950cebfb4916ac1 schema:name doi
64 schema:value 10.1007/978-3-642-00202-1_15
65 rdf:type schema:PropertyValue
66 Ne6f02641159843e996c5d8ee1ba7fb4b rdf:first Naf0c40ec479d4e1ba7273ac7500c0e1e
67 rdf:rest rdf:nil
68 Nf22397d33b4f49e093c8b0952029a54c schema:name dimensions_id
69 schema:value pub.1003057903
70 rdf:type schema:PropertyValue
71 Nf96ffbeeb6fc43238ceebb80124da314 rdf:first sg:person.012173062656.50
72 rdf:rest Na6bc83ed68bc40308f157aeee868174a
73 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
74 schema:name Information and Computing Sciences
75 rdf:type schema:DefinedTerm
76 anzsrc-for:0801 schema:inDefinedTermSet anzsrc-for:
77 schema:name Artificial Intelligence and Image Processing
78 rdf:type schema:DefinedTerm
79 sg:person.011402427702.78 schema:affiliation https://www.grid.ac/institutes/grid.7841.a
80 schema:familyName Petreschi
81 schema:givenName Rossella
82 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011402427702.78
83 rdf:type schema:Person
84 sg:person.012173062656.50 schema:affiliation https://www.grid.ac/institutes/grid.7841.a
85 schema:familyName Borri
86 schema:givenName Alessandro
87 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012173062656.50
88 rdf:type schema:Person
89 sg:person.013577775161.22 schema:affiliation https://www.grid.ac/institutes/grid.7841.a
90 schema:familyName Calamoneri
91 schema:givenName Tiziana
92 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013577775161.22
93 rdf:type schema:Person
94 https://doi.org/10.1002/sapm1975544283 schema:sameAs https://app.dimensions.ai/details/publication/pub.1012144983
95 rdf:type schema:CreativeWork
96 https://doi.org/10.1016/0012-365x(84)90023-2 schema:sameAs https://app.dimensions.ai/details/publication/pub.1001514301
97 rdf:type schema:CreativeWork
98 https://doi.org/10.1016/0012-365x(84)90026-8 schema:sameAs https://app.dimensions.ai/details/publication/pub.1038841355
99 rdf:type schema:CreativeWork
100 https://doi.org/10.1016/j.dam.2006.03.036 schema:sameAs https://app.dimensions.ai/details/publication/pub.1048103103
101 rdf:type schema:CreativeWork
102 https://doi.org/10.1016/s0012-365x(96)00171-9 schema:sameAs https://app.dimensions.ai/details/publication/pub.1020072806
103 rdf:type schema:CreativeWork
104 https://doi.org/10.1016/s0012-365x(99)00381-7 schema:sameAs https://app.dimensions.ai/details/publication/pub.1019371700
105 rdf:type schema:CreativeWork
106 https://doi.org/10.1016/s0020-0190(00)00041-7 schema:sameAs https://app.dimensions.ai/details/publication/pub.1033464701
107 rdf:type schema:CreativeWork
108 https://doi.org/10.1016/s0095-8956(76)80007-x schema:sameAs https://app.dimensions.ai/details/publication/pub.1006901821
109 rdf:type schema:CreativeWork
110 https://doi.org/10.1016/s0167-5060(08)70731-3 schema:sameAs https://app.dimensions.ai/details/publication/pub.1046754752
111 rdf:type schema:CreativeWork
112 https://doi.org/10.1016/s0167-5060(08)70749-0 schema:sameAs https://app.dimensions.ai/details/publication/pub.1015050349
113 rdf:type schema:CreativeWork
114 https://doi.org/10.1137/0110037 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062837838
115 rdf:type schema:CreativeWork
116 https://doi.org/10.2140/pjm.1975.56.143 schema:sameAs https://app.dimensions.ai/details/publication/pub.1069066208
117 rdf:type schema:CreativeWork
118 https://www.grid.ac/institutes/grid.7841.a schema:alternateName Sapienza University of Rome
119 schema:name Department of Computer Science, Univ. of Rome “Sapienza” - Italy, via Salaria 113, 00198, Roma, Italy
120 rdf:type schema:Organization
 




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


...