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

References to SciGraph publications

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 Nf21faff4207a45d5a397b21e20f884fb
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 N67319ae49ae94bd4ac56bf2e89609101
19 Nc70f689e62414233b43623fa8b988aa3
20 sg:journal.1356894
21 schema:name Graph isomorphism: A heuristic edge-partitioning-oriented algorithm
22 schema:pagination 291-313
23 schema:productId N3e861e5513d64687a83e925f8bb39c24
24 N7ad441c1fc1848069df4a4c13258dd3e
25 Na098ed8fd6774fb890667225a493c80a
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 N613d9d9c9fd042cfa42b106c07e10e03
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 N3e861e5513d64687a83e925f8bb39c24 schema:name dimensions_id
36 schema:value pub.1034909802
37 rdf:type schema:PropertyValue
38 N613d9d9c9fd042cfa42b106c07e10e03 schema:name Springer Nature - SN SciGraph project
39 rdf:type schema:Organization
40 N67319ae49ae94bd4ac56bf2e89609101 schema:issueNumber 4
41 rdf:type schema:PublicationIssue
42 N7ad441c1fc1848069df4a4c13258dd3e schema:name readcube_id
43 schema:value a64c3c6c0a1dc52fe1d78a658d2f1e5cd294b497eb8ac7c9b4dc0b515b38ff25
44 rdf:type schema:PropertyValue
45 Na098ed8fd6774fb890667225a493c80a schema:name doi
46 schema:value 10.1007/bf02253334
47 rdf:type schema:PropertyValue
48 Nc70f689e62414233b43623fa8b988aa3 schema:volumeNumber 12
49 rdf:type schema:PublicationVolume
50 Ndc7076f1391d4853830f689673b41f69 schema:affiliation https://www.grid.ac/institutes/grid.5326.2
51 schema:familyName Levi
52 schema:givenName G.
53 rdf:type schema:Person
54 Nf21faff4207a45d5a397b21e20f884fb rdf:first Ndc7076f1391d4853830f689673b41f69
55 rdf:rest rdf:nil
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)


...