A new algorithm for digraph isomorphism View Full Text


Ontology type: schema:ScholarlyArticle     


Article Info

DATE

1977-03

AUTHORS

Narsingh Deo, J. M. Davis, R. E. Lord

ABSTRACT

A new and efficient procedure for testing a pair of digraphs for isomorphism is developed. It is based on conducting a depth-first search on one of the digraphs followed by a systematic matching of edges using backtracking with very effective pruning. It is proved that for digraphs (ofn vertices) the expected time complexity of this procedure isO(nlogn). This theoretical result is verified empirically on more than 300 large random digraphs. This procedure is shown to be more efficient than any of the existing general isomorphism procedures. More... »

PAGES

16-30

References to SciGraph publications

  • 1974-06. Search for a unique incidence matrix of a graph in BIT NUMERICAL MATHEMATICS
  • 1972. Reducibility among Combinatorial Problems in COMPLEXITY OF COMPUTER COMPUTATIONS
  • 1974-12. Graph isomorphism: A heuristic edge-partitioning-oriented algorithm in COMPUTING
  • Identifiers

    URI

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

    DOI

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

    DIMENSIONS

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


    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/1701", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Psychology", 
            "type": "DefinedTerm"
          }, 
          {
            "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/17", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Psychology and Cognitive Sciences", 
            "type": "DefinedTerm"
          }
        ], 
        "author": [
          {
            "affiliation": {
              "alternateName": "Montana State University", 
              "id": "https://www.grid.ac/institutes/grid.41891.35", 
              "name": [
                "Indian Institute of Technology, Kanpur, India", 
                "Weyerhaeuser Company, Tacoma, Washington, U.S.A.", 
                "Montana State University, Bozeman, Montana, U.S.A."
              ], 
              "type": "Organization"
            }, 
            "familyName": "Deo", 
            "givenName": "Narsingh", 
            "id": "sg:person.010274011142.47", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010274011142.47"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "Montana State University", 
              "id": "https://www.grid.ac/institutes/grid.41891.35", 
              "name": [
                "Indian Institute of Technology, Kanpur, India", 
                "Weyerhaeuser Company, Tacoma, Washington, U.S.A.", 
                "Montana State University, Bozeman, Montana, U.S.A."
              ], 
              "type": "Organization"
            }, 
            "familyName": "Davis", 
            "givenName": "J. M.", 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "Montana State University", 
              "id": "https://www.grid.ac/institutes/grid.41891.35", 
              "name": [
                "Indian Institute of Technology, Kanpur, India", 
                "Weyerhaeuser Company, Tacoma, Washington, U.S.A.", 
                "Montana State University, Bozeman, Montana, U.S.A."
              ], 
              "type": "Organization"
            }, 
            "familyName": "Lord", 
            "givenName": "R. E.", 
            "type": "Person"
          }
        ], 
        "citation": [
          {
            "id": "https://doi.org/10.1145/321556.321562", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1003980246"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-1-4684-2001-2_9", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1007977430", 
              "https://doi.org/10.1007/978-1-4684-2001-2_9"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/321921.321925", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1008268655"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/363872.363899", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1015364039"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1112/blms/3.3.321", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1025984649"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/362248.362272", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1026240786"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf02253334", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1034909802", 
              "https://doi.org/10.1007/bf02253334"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf02253334", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1034909802", 
              "https://doi.org/10.1007/bf02253334"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf01932948", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1048143115", 
              "https://doi.org/10.1007/bf01932948"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf01932948", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1048143115", 
              "https://doi.org/10.1007/bf01932948"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/321765.321766", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1050081283"
            ], 
            "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.1137/0201010", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1062841173"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "1977-03", 
        "datePublishedReg": "1977-03-01", 
        "description": "A new and efficient procedure for testing a pair of digraphs for isomorphism is developed. It is based on conducting a depth-first search on one of the digraphs followed by a systematic matching of edges using backtracking with very effective pruning. It is proved that for digraphs (ofn vertices) the expected time complexity of this procedure isO(nlogn). This theoretical result is verified empirically on more than 300 large random digraphs. This procedure is shown to be more efficient than any of the existing general isomorphism procedures.", 
        "genre": "research_article", 
        "id": "sg:pub.10.1007/bf01932396", 
        "inLanguage": [
          "en"
        ], 
        "isAccessibleForFree": false, 
        "isPartOf": [
          {
            "id": "sg:journal.1136252", 
            "issn": [
              "0006-3835", 
              "1572-9125"
            ], 
            "name": "BIT Numerical Mathematics", 
            "type": "Periodical"
          }, 
          {
            "issueNumber": "1", 
            "type": "PublicationIssue"
          }, 
          {
            "type": "PublicationVolume", 
            "volumeNumber": "17"
          }
        ], 
        "name": "A new algorithm for digraph isomorphism", 
        "pagination": "16-30", 
        "productId": [
          {
            "name": "readcube_id", 
            "type": "PropertyValue", 
            "value": [
              "99796c1a79f18c5a22ef789d97b4199344009392e7612a6a79c7c712f4dc227c"
            ]
          }, 
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1007/bf01932396"
            ]
          }, 
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1032216811"
            ]
          }
        ], 
        "sameAs": [
          "https://doi.org/10.1007/bf01932396", 
          "https://app.dimensions.ai/details/publication/pub.1032216811"
        ], 
        "sdDataset": "articles", 
        "sdDatePublished": "2019-04-10T18: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_8675_00000489.jsonl", 
        "type": "ScholarlyArticle", 
        "url": "http://link.springer.com/10.1007/BF01932396"
      }
    ]
     

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

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

    Turtle is a human-readable linked data format.

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

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

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


     

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

    111 TRIPLES      21 PREDICATES      38 URIs      19 LITERALS      7 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/bf01932396 schema:about anzsrc-for:17
    2 anzsrc-for:1701
    3 schema:author N9123715bdb234914b767414580526d4c
    4 schema:citation sg:pub.10.1007/978-1-4684-2001-2_9
    5 sg:pub.10.1007/bf01932948
    6 sg:pub.10.1007/bf02253334
    7 https://doi.org/10.1021/c160016a007
    8 https://doi.org/10.1112/blms/3.3.321
    9 https://doi.org/10.1137/0201010
    10 https://doi.org/10.1145/321556.321562
    11 https://doi.org/10.1145/321765.321766
    12 https://doi.org/10.1145/321921.321925
    13 https://doi.org/10.1145/362248.362272
    14 https://doi.org/10.1145/363872.363899
    15 schema:datePublished 1977-03
    16 schema:datePublishedReg 1977-03-01
    17 schema:description A new and efficient procedure for testing a pair of digraphs for isomorphism is developed. It is based on conducting a depth-first search on one of the digraphs followed by a systematic matching of edges using backtracking with very effective pruning. It is proved that for digraphs (ofn vertices) the expected time complexity of this procedure isO(nlogn). This theoretical result is verified empirically on more than 300 large random digraphs. This procedure is shown to be more efficient than any of the existing general isomorphism procedures.
    18 schema:genre research_article
    19 schema:inLanguage en
    20 schema:isAccessibleForFree false
    21 schema:isPartOf N04b547f358f64142ab2058161e39e23d
    22 Nb12c60c8815e4a5e8c7d6315d5bf9299
    23 sg:journal.1136252
    24 schema:name A new algorithm for digraph isomorphism
    25 schema:pagination 16-30
    26 schema:productId N4f94029a1c6840f0851a19f4d703d868
    27 Nca488d4e46b6411b95035d7c7c168dae
    28 Nd07658d567fe45178f58e3b0934af319
    29 schema:sameAs https://app.dimensions.ai/details/publication/pub.1032216811
    30 https://doi.org/10.1007/bf01932396
    31 schema:sdDatePublished 2019-04-10T18:15
    32 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    33 schema:sdPublisher N6d8dcf2671af4752a819fefff5264906
    34 schema:url http://link.springer.com/10.1007/BF01932396
    35 sgo:license sg:explorer/license/
    36 sgo:sdDataset articles
    37 rdf:type schema:ScholarlyArticle
    38 N0443886869fe44bfb09cc731433e4f99 rdf:first Na55fe8fa7de64bae99168503bef8cd7c
    39 rdf:rest Ne3061bf241cc4519bcc8b63128175832
    40 N04b547f358f64142ab2058161e39e23d schema:issueNumber 1
    41 rdf:type schema:PublicationIssue
    42 N4f94029a1c6840f0851a19f4d703d868 schema:name readcube_id
    43 schema:value 99796c1a79f18c5a22ef789d97b4199344009392e7612a6a79c7c712f4dc227c
    44 rdf:type schema:PropertyValue
    45 N6d8dcf2671af4752a819fefff5264906 schema:name Springer Nature - SN SciGraph project
    46 rdf:type schema:Organization
    47 N9123715bdb234914b767414580526d4c rdf:first sg:person.010274011142.47
    48 rdf:rest N0443886869fe44bfb09cc731433e4f99
    49 Na55fe8fa7de64bae99168503bef8cd7c schema:affiliation https://www.grid.ac/institutes/grid.41891.35
    50 schema:familyName Davis
    51 schema:givenName J. M.
    52 rdf:type schema:Person
    53 Nb12c60c8815e4a5e8c7d6315d5bf9299 schema:volumeNumber 17
    54 rdf:type schema:PublicationVolume
    55 Nca488d4e46b6411b95035d7c7c168dae schema:name dimensions_id
    56 schema:value pub.1032216811
    57 rdf:type schema:PropertyValue
    58 Nd07658d567fe45178f58e3b0934af319 schema:name doi
    59 schema:value 10.1007/bf01932396
    60 rdf:type schema:PropertyValue
    61 Ne06500d8cf8243c6854e617ed97e0de2 schema:affiliation https://www.grid.ac/institutes/grid.41891.35
    62 schema:familyName Lord
    63 schema:givenName R. E.
    64 rdf:type schema:Person
    65 Ne3061bf241cc4519bcc8b63128175832 rdf:first Ne06500d8cf8243c6854e617ed97e0de2
    66 rdf:rest rdf:nil
    67 anzsrc-for:17 schema:inDefinedTermSet anzsrc-for:
    68 schema:name Psychology and Cognitive Sciences
    69 rdf:type schema:DefinedTerm
    70 anzsrc-for:1701 schema:inDefinedTermSet anzsrc-for:
    71 schema:name Psychology
    72 rdf:type schema:DefinedTerm
    73 sg:journal.1136252 schema:issn 0006-3835
    74 1572-9125
    75 schema:name BIT Numerical Mathematics
    76 rdf:type schema:Periodical
    77 sg:person.010274011142.47 schema:affiliation https://www.grid.ac/institutes/grid.41891.35
    78 schema:familyName Deo
    79 schema:givenName Narsingh
    80 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010274011142.47
    81 rdf:type schema:Person
    82 sg:pub.10.1007/978-1-4684-2001-2_9 schema:sameAs https://app.dimensions.ai/details/publication/pub.1007977430
    83 https://doi.org/10.1007/978-1-4684-2001-2_9
    84 rdf:type schema:CreativeWork
    85 sg:pub.10.1007/bf01932948 schema:sameAs https://app.dimensions.ai/details/publication/pub.1048143115
    86 https://doi.org/10.1007/bf01932948
    87 rdf:type schema:CreativeWork
    88 sg:pub.10.1007/bf02253334 schema:sameAs https://app.dimensions.ai/details/publication/pub.1034909802
    89 https://doi.org/10.1007/bf02253334
    90 rdf:type schema:CreativeWork
    91 https://doi.org/10.1021/c160016a007 schema:sameAs https://app.dimensions.ai/details/publication/pub.1055225028
    92 rdf:type schema:CreativeWork
    93 https://doi.org/10.1112/blms/3.3.321 schema:sameAs https://app.dimensions.ai/details/publication/pub.1025984649
    94 rdf:type schema:CreativeWork
    95 https://doi.org/10.1137/0201010 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062841173
    96 rdf:type schema:CreativeWork
    97 https://doi.org/10.1145/321556.321562 schema:sameAs https://app.dimensions.ai/details/publication/pub.1003980246
    98 rdf:type schema:CreativeWork
    99 https://doi.org/10.1145/321765.321766 schema:sameAs https://app.dimensions.ai/details/publication/pub.1050081283
    100 rdf:type schema:CreativeWork
    101 https://doi.org/10.1145/321921.321925 schema:sameAs https://app.dimensions.ai/details/publication/pub.1008268655
    102 rdf:type schema:CreativeWork
    103 https://doi.org/10.1145/362248.362272 schema:sameAs https://app.dimensions.ai/details/publication/pub.1026240786
    104 rdf:type schema:CreativeWork
    105 https://doi.org/10.1145/363872.363899 schema:sameAs https://app.dimensions.ai/details/publication/pub.1015364039
    106 rdf:type schema:CreativeWork
    107 https://www.grid.ac/institutes/grid.41891.35 schema:alternateName Montana State University
    108 schema:name Indian Institute of Technology, Kanpur, India
    109 Montana State University, Bozeman, Montana, U.S.A.
    110 Weyerhaeuser Company, Tacoma, Washington, U.S.A.
    111 rdf:type schema:Organization
     




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


    ...