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 N27c7d2c8e06a42ca88b6628b2d673d99
    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 N240d18289355483380e79b29766fe58d
    22 Nafc251515eca4e84a39a2e0b3ede852f
    23 sg:journal.1136252
    24 schema:name A new algorithm for digraph isomorphism
    25 schema:pagination 16-30
    26 schema:productId N0543a1ecf6624805b6be4ec497cacaef
    27 N565ec3be8d7d4a15943f7fa62424859a
    28 N8bac96ecdefd4d7aac149eb53da50d22
    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 N0ee5fd351bcd4f6b9a1f275f5d7e62b5
    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 N0543a1ecf6624805b6be4ec497cacaef schema:name dimensions_id
    39 schema:value pub.1032216811
    40 rdf:type schema:PropertyValue
    41 N0ee5fd351bcd4f6b9a1f275f5d7e62b5 schema:name Springer Nature - SN SciGraph project
    42 rdf:type schema:Organization
    43 N0ff6c799456642f69caa05a644f26db9 rdf:first N50a954f3c33e471aa06128bfe0d25a79
    44 rdf:rest rdf:nil
    45 N240d18289355483380e79b29766fe58d schema:volumeNumber 17
    46 rdf:type schema:PublicationVolume
    47 N27c7d2c8e06a42ca88b6628b2d673d99 rdf:first sg:person.010274011142.47
    48 rdf:rest N8ee3d9eb50f8493bada9ff25005aab3d
    49 N34fe2158d3224e1293850e91807c5208 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 N50a954f3c33e471aa06128bfe0d25a79 schema:affiliation https://www.grid.ac/institutes/grid.41891.35
    54 schema:familyName Lord
    55 schema:givenName R. E.
    56 rdf:type schema:Person
    57 N565ec3be8d7d4a15943f7fa62424859a schema:name doi
    58 schema:value 10.1007/bf01932396
    59 rdf:type schema:PropertyValue
    60 N8bac96ecdefd4d7aac149eb53da50d22 schema:name readcube_id
    61 schema:value 99796c1a79f18c5a22ef789d97b4199344009392e7612a6a79c7c712f4dc227c
    62 rdf:type schema:PropertyValue
    63 N8ee3d9eb50f8493bada9ff25005aab3d rdf:first N34fe2158d3224e1293850e91807c5208
    64 rdf:rest N0ff6c799456642f69caa05a644f26db9
    65 Nafc251515eca4e84a39a2e0b3ede852f schema:issueNumber 1
    66 rdf:type schema:PublicationIssue
    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)


    ...