Graph isomorphism: A heuristic edge-partitioning-oriented algorithm View Full Text


Ontology type: schema:ScholarlyArticle     


Article Info

DATE

1974-12

AUTHORS

G. Levi

ABSTRACT

A new algorithm for testing isomorphism on directed and undirected graphs is described. It consists of an 0 (n5) algorithm for partitioning node and edge sets, plus a heuristic procedure for deriving all the isomorphisms. The partitioning is described by a “connectivity graph” on which a sufficient condition for isomerphism can be tested. More... »

PAGES

291-313

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/bf02253334

DOI

http://dx.doi.org/10.1007/bf02253334

DIMENSIONS

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


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": "National Research Council", 
          "id": "https://www.grid.ac/institutes/grid.5326.2", 
          "name": [
            "Istituto di Elaborazione dell'Informazione, Consiglio Nazionale delle Ricerche, Via S. Maria, 46, I-56100, Pisa, Italy"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Levi", 
        "givenName": "G.", 
        "type": "Person"
      }
    ], 
    "citation": [
      {
        "id": "https://doi.org/10.1145/321556.321562", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1003980246"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/363872.363899", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1015364039"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bf02575571", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1016989261", 
          "https://doi.org/10.1007/bf02575571"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bf02575800", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1028788771", 
          "https://doi.org/10.1007/bf02575800"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bf02575800", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1028788771", 
          "https://doi.org/10.1007/bf02575800"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bf02575547", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1031337157", 
          "https://doi.org/10.1007/bf02575547"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bf02575586", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1041808659", 
          "https://doi.org/10.1007/bf02575586"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bf02575586", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1041808659", 
          "https://doi.org/10.1007/bf02575586"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1021/c160016a007", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1055225028"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.4153/cjm-1967-091-8", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1072264939"
        ], 
        "type": "CreativeWork"
      }
    ], 
    "datePublished": "1974-12", 
    "datePublishedReg": "1974-12-01", 
    "description": "A new algorithm for testing isomorphism on directed and undirected graphs is described. It consists of an 0 (n5) algorithm for partitioning node and edge sets, plus a heuristic procedure for deriving all the isomorphisms. The partitioning is described by a \u201cconnectivity graph\u201d on which a sufficient condition for isomerphism can be tested.", 
    "genre": "research_article", 
    "id": "sg:pub.10.1007/bf02253334", 
    "inLanguage": [
      "en"
    ], 
    "isAccessibleForFree": false, 
    "isPartOf": [
      {
        "id": "sg:journal.1356894", 
        "issn": [
          "1521-9615", 
          "1436-5057"
        ], 
        "name": "Computing", 
        "type": "Periodical"
      }, 
      {
        "issueNumber": "4", 
        "type": "PublicationIssue"
      }, 
      {
        "type": "PublicationVolume", 
        "volumeNumber": "12"
      }
    ], 
    "name": "Graph isomorphism: A heuristic edge-partitioning-oriented algorithm", 
    "pagination": "291-313", 
    "productId": [
      {
        "name": "readcube_id", 
        "type": "PropertyValue", 
        "value": [
          "a64c3c6c0a1dc52fe1d78a658d2f1e5cd294b497eb8ac7c9b4dc0b515b38ff25"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/bf02253334"
        ]
      }, 
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1034909802"
        ]
      }
    ], 
    "sameAs": [
      "https://doi.org/10.1007/bf02253334", 
      "https://app.dimensions.ai/details/publication/pub.1034909802"
    ], 
    "sdDataset": "articles", 
    "sdDatePublished": "2019-04-11T12:21", 
    "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/0000000362_0000000362/records_87079_00000001.jsonl", 
    "type": "ScholarlyArticle", 
    "url": "http://link.springer.com/10.1007%2FBF02253334"
  }
]
 

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/bf02253334'

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/bf02253334'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/bf02253334'

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

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/bf02253334'


 

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

88 TRIPLES      21 PREDICATES      35 URIs      19 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/bf02253334 schema:about anzsrc-for:08
2 anzsrc-for:0802
3 schema:author N011e1d025e4c4822b5d090335d4f9a30
4 schema:citation sg:pub.10.1007/bf02575547
5 sg:pub.10.1007/bf02575571
6 sg:pub.10.1007/bf02575586
7 sg:pub.10.1007/bf02575800
8 https://doi.org/10.1021/c160016a007
9 https://doi.org/10.1145/321556.321562
10 https://doi.org/10.1145/363872.363899
11 https://doi.org/10.4153/cjm-1967-091-8
12 schema:datePublished 1974-12
13 schema:datePublishedReg 1974-12-01
14 schema:description A new algorithm for testing isomorphism on directed and undirected graphs is described. It consists of an 0 (n5) algorithm for partitioning node and edge sets, plus a heuristic procedure for deriving all the isomorphisms. The partitioning is described by a “connectivity graph” on which a sufficient condition for isomerphism can be tested.
15 schema:genre research_article
16 schema:inLanguage en
17 schema:isAccessibleForFree false
18 schema:isPartOf Ndbbb83156c72428a8ef80acf007f0b64
19 Ndeb6fe11e8af40619874e1890e1a7f6a
20 sg:journal.1356894
21 schema:name Graph isomorphism: A heuristic edge-partitioning-oriented algorithm
22 schema:pagination 291-313
23 schema:productId Nd817c8abef8e49de8e9408dccc52bfc2
24 Ne1c4e6cc53f446459d9e9f7bb6d222e7
25 Ne8cba4532f10421485d6b388b2277e3d
26 schema:sameAs https://app.dimensions.ai/details/publication/pub.1034909802
27 https://doi.org/10.1007/bf02253334
28 schema:sdDatePublished 2019-04-11T12:21
29 schema:sdLicense https://scigraph.springernature.com/explorer/license/
30 schema:sdPublisher N63f5fa5f0aff4276b20a4d707630e4a0
31 schema:url http://link.springer.com/10.1007%2FBF02253334
32 sgo:license sg:explorer/license/
33 sgo:sdDataset articles
34 rdf:type schema:ScholarlyArticle
35 N011e1d025e4c4822b5d090335d4f9a30 rdf:first N30ffdcd6d9184c86a4b2b3727521b883
36 rdf:rest rdf:nil
37 N30ffdcd6d9184c86a4b2b3727521b883 schema:affiliation https://www.grid.ac/institutes/grid.5326.2
38 schema:familyName Levi
39 schema:givenName G.
40 rdf:type schema:Person
41 N63f5fa5f0aff4276b20a4d707630e4a0 schema:name Springer Nature - SN SciGraph project
42 rdf:type schema:Organization
43 Nd817c8abef8e49de8e9408dccc52bfc2 schema:name doi
44 schema:value 10.1007/bf02253334
45 rdf:type schema:PropertyValue
46 Ndbbb83156c72428a8ef80acf007f0b64 schema:issueNumber 4
47 rdf:type schema:PublicationIssue
48 Ndeb6fe11e8af40619874e1890e1a7f6a schema:volumeNumber 12
49 rdf:type schema:PublicationVolume
50 Ne1c4e6cc53f446459d9e9f7bb6d222e7 schema:name readcube_id
51 schema:value a64c3c6c0a1dc52fe1d78a658d2f1e5cd294b497eb8ac7c9b4dc0b515b38ff25
52 rdf:type schema:PropertyValue
53 Ne8cba4532f10421485d6b388b2277e3d schema:name dimensions_id
54 schema:value pub.1034909802
55 rdf:type schema:PropertyValue
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.1356894 schema:issn 1436-5057
63 1521-9615
64 schema:name Computing
65 rdf:type schema:Periodical
66 sg:pub.10.1007/bf02575547 schema:sameAs https://app.dimensions.ai/details/publication/pub.1031337157
67 https://doi.org/10.1007/bf02575547
68 rdf:type schema:CreativeWork
69 sg:pub.10.1007/bf02575571 schema:sameAs https://app.dimensions.ai/details/publication/pub.1016989261
70 https://doi.org/10.1007/bf02575571
71 rdf:type schema:CreativeWork
72 sg:pub.10.1007/bf02575586 schema:sameAs https://app.dimensions.ai/details/publication/pub.1041808659
73 https://doi.org/10.1007/bf02575586
74 rdf:type schema:CreativeWork
75 sg:pub.10.1007/bf02575800 schema:sameAs https://app.dimensions.ai/details/publication/pub.1028788771
76 https://doi.org/10.1007/bf02575800
77 rdf:type schema:CreativeWork
78 https://doi.org/10.1021/c160016a007 schema:sameAs https://app.dimensions.ai/details/publication/pub.1055225028
79 rdf:type schema:CreativeWork
80 https://doi.org/10.1145/321556.321562 schema:sameAs https://app.dimensions.ai/details/publication/pub.1003980246
81 rdf:type schema:CreativeWork
82 https://doi.org/10.1145/363872.363899 schema:sameAs https://app.dimensions.ai/details/publication/pub.1015364039
83 rdf:type schema:CreativeWork
84 https://doi.org/10.4153/cjm-1967-091-8 schema:sameAs https://app.dimensions.ai/details/publication/pub.1072264939
85 rdf:type schema:CreativeWork
86 https://www.grid.ac/institutes/grid.5326.2 schema:alternateName National Research Council
87 schema:name Istituto di Elaborazione dell'Informazione, Consiglio Nazionale delle Ricerche, Via S. Maria, 46, I-56100, Pisa, Italy
88 rdf:type schema:Organization
 




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


...