Fast Subgraph Matching Strategies Based on Pattern-Only Heuristics View Full Text


Ontology type: schema:ScholarlyArticle     


Article Info

DATE

2019-03

AUTHORS

Antonino Aparo, Vincenzo Bonnici, Giovanni Micale, Alfredo Ferro, Dennis Shasha, Alfredo Pulvirenti, Rosalba Giugno

ABSTRACT

Many scientific applications entail solving the subgraph isomorphism problem, i.e., given an input pattern graph, find all the subgraphs of a (usually much larger) target graph that are structurally equivalent to that input. Because subgraph isomorphism is NP-complete, methods to solve it have to use heuristics. This work evaluates subgraph isomorphism methods to assess their computational behavior on a wide range of synthetic and real graphs. Surprisingly, our experiments show that, among the leading algorithms, certain heuristics based only on pattern graphs are the most efficient. More... »

PAGES

21-32

References to SciGraph publications

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/s12539-019-00323-0

DOI

http://dx.doi.org/10.1007/s12539-019-00323-0

DIMENSIONS

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

PUBMED

https://www.ncbi.nlm.nih.gov/pubmed/30790228


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": "University of Verona", 
          "id": "https://www.grid.ac/institutes/grid.5611.3", 
          "name": [
            "Department of Computer Science, University of Verona, Verona, Italy"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Aparo", 
        "givenName": "Antonino", 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "University of Verona", 
          "id": "https://www.grid.ac/institutes/grid.5611.3", 
          "name": [
            "Department of Computer Science, University of Verona, Verona, Italy"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Bonnici", 
        "givenName": "Vincenzo", 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "University of Catania", 
          "id": "https://www.grid.ac/institutes/grid.8158.4", 
          "name": [
            "Department of Clinical and Experimental Medicine, University of Catania, Catania, Italy"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Micale", 
        "givenName": "Giovanni", 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "University of Catania", 
          "id": "https://www.grid.ac/institutes/grid.8158.4", 
          "name": [
            "Department of Clinical and Experimental Medicine, University of Catania, Catania, Italy"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Ferro", 
        "givenName": "Alfredo", 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Courant Institute of Mathematical Sciences", 
          "id": "https://www.grid.ac/institutes/grid.482020.c", 
          "name": [
            "Computer Science Department, Courant Institute, New York University, New York, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Shasha", 
        "givenName": "Dennis", 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "University of Catania", 
          "id": "https://www.grid.ac/institutes/grid.8158.4", 
          "name": [
            "Department of Clinical and Experimental Medicine, University of Catania, Catania, Italy"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Pulvirenti", 
        "givenName": "Alfredo", 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "University of Verona", 
          "id": "https://www.grid.ac/institutes/grid.5611.3", 
          "name": [
            "Department of Computer Science, University of Verona, Verona, Italy"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Giugno", 
        "givenName": "Rosalba", 
        "type": "Person"
      }
    ], 
    "citation": [
      {
        "id": "sg:pub.10.1891/0739-6686.29.55", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1005609973", 
          "https://doi.org/10.1891/0739-6686.29.55"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.12688/f1000research.4537.2", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1007578244"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.12688/f1000research.4537.2", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1007578244"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1371/journal.pone.0098750", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1008955663"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1002/wsbm.37", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1009562848"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1126/science.286.5439.509", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1010080128"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.3389/fbioe.2015.00058", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1010674371"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1093/bioinformatics/btl301", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1010804001"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/210332.210337", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1011509889"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-3-642-13731-0_9", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1013527218", 
          "https://doi.org/10.1007/978-3-642-13731-0_9"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-3-642-13731-0_9", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1013527218", 
          "https://doi.org/10.1007/978-3-642-13731-0_9"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.3389/fgene.2014.00302", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1013885289"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/1671970.1921702", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1014512066"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1126/science.1091403", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1015172314"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1093/bfgp/els032", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1016403562"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1038/nrg1272", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1018231980", 
          "https://doi.org/10.1038/nrg1272"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1038/nrg1272", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1018231980", 
          "https://doi.org/10.1038/nrg1272"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1126/science.1073374", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1019781582"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1038/nchembio.462", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1020048109", 
          "https://doi.org/10.1038/nchembio.462"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1038/nchembio.462", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1020048109", 
          "https://doi.org/10.1038/nchembio.462"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/1081870.1081893", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1020085889"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1038/nrg2918", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1021371713", 
          "https://doi.org/10.1038/nrg2918"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1038/nrg2918", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1021371713", 
          "https://doi.org/10.1038/nrg2918"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.3389/fgene.2014.00083", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1022436615"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1073/pnas.2133841100", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1023151304"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1371/journal.pone.0076911", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1024443802"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1093/nar/gkq1039", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1026557089"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/s11103-005-8159-7", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1028739512", 
          "https://doi.org/10.1007/s11103-005-8159-7"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/s11103-005-8159-7", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1028739512", 
          "https://doi.org/10.1007/s11103-005-8159-7"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1038/nature11245", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1028790868", 
          "https://doi.org/10.1038/nature11245"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1186/1471-2105-14-s7-s13", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1028830970", 
          "https://doi.org/10.1186/1471-2105-14-s7-s13"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1186/1471-2105-14-s7-s13", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1028830970", 
          "https://doi.org/10.1186/1471-2105-14-s7-s13"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.5808/gi.2013.11.4.200", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1030838547"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1093/bfgp/els037", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1033002789"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1126/science.298.5594.824", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1033238539"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/0020-0255(79)90023-9", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1036030687"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/0020-0255(79)90023-9", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1036030687"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/j.pharmthera.2013.01.016", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1036857532"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1186/1471-2105-12-45", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1039226122", 
          "https://doi.org/10.1186/1471-2105-12-45"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/j.artint.2010.05.002", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1039626128"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1093/nar/gkt1190", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1039838368"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1093/nar/gkw1102", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1041939167"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1140/epjb/e2004-00301-0", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1045239815", 
          "https://doi.org/10.1140/epjb/e2004-00301-0"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1093/nar/gks1094", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1045624288"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/0004-3702(80)90051-x", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1045789426"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/0004-3702(80)90051-x", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1045789426"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1093/nar/gkj126", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1049555345"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.3389/fbioe.2014.00069", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1050267577"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1049/iet-syb:20060071", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1056839183"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1093/bioinformatics/btw223", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1059414750"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1109/tcbb.2016.2515595", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1061541576"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1109/tpami.2004.75", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1061742753"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.14304/surya.jpr.v1n1.7", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1067261424"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.14778/2535568.2448946", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1067368130"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.4137/cin.s680", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1077858174"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.4137/cin.s680", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1077858174"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-981-10-5508-9_30", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1092166189", 
          "https://doi.org/10.1007/978-981-10-5508-9_30"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/s10618-017-0544-8", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1092500787", 
          "https://doi.org/10.1007/s10618-017-0544-8"
        ], 
        "type": "CreativeWork"
      }
    ], 
    "datePublished": "2019-03", 
    "datePublishedReg": "2019-03-01", 
    "description": "Many scientific applications entail solving the subgraph isomorphism problem, i.e., given an input pattern graph, find all the subgraphs of a (usually much larger) target graph that are structurally equivalent to that input. Because subgraph isomorphism is NP-complete, methods to solve it have to use heuristics. This work evaluates subgraph isomorphism methods to assess their computational behavior on a wide range of synthetic and real graphs. Surprisingly, our experiments show that, among the leading algorithms, certain heuristics based only on pattern graphs are the most efficient.", 
    "genre": "research_article", 
    "id": "sg:pub.10.1007/s12539-019-00323-0", 
    "inLanguage": [
      "en"
    ], 
    "isAccessibleForFree": false, 
    "isFundedItemOf": [
      {
        "id": "sg:grant.3135072", 
        "type": "MonetaryGrant"
      }, 
      {
        "id": "sg:grant.3580241", 
        "type": "MonetaryGrant"
      }, 
      {
        "id": "sg:grant.3848075", 
        "type": "MonetaryGrant"
      }
    ], 
    "isPartOf": [
      {
        "id": "sg:journal.1042186", 
        "issn": [
          "1913-2751", 
          "1867-1462"
        ], 
        "name": "Interdisciplinary Sciences: Computational Life Sciences", 
        "type": "Periodical"
      }, 
      {
        "issueNumber": "1", 
        "type": "PublicationIssue"
      }, 
      {
        "type": "PublicationVolume", 
        "volumeNumber": "11"
      }
    ], 
    "name": "Fast Subgraph Matching Strategies Based on Pattern-Only Heuristics", 
    "pagination": "21-32", 
    "productId": [
      {
        "name": "readcube_id", 
        "type": "PropertyValue", 
        "value": [
          "64faa2c4ce3d6c04b9d088d8c1cb813b622f074a5251563a3ed91b7c8b6f3ff7"
        ]
      }, 
      {
        "name": "pubmed_id", 
        "type": "PropertyValue", 
        "value": [
          "30790228"
        ]
      }, 
      {
        "name": "nlm_unique_id", 
        "type": "PropertyValue", 
        "value": [
          "101515919"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/s12539-019-00323-0"
        ]
      }, 
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1112283476"
        ]
      }
    ], 
    "sameAs": [
      "https://doi.org/10.1007/s12539-019-00323-0", 
      "https://app.dimensions.ai/details/publication/pub.1112283476"
    ], 
    "sdDataset": "articles", 
    "sdDatePublished": "2019-04-11T11:24", 
    "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/0000000355_0000000355/records_53007_00000000.jsonl", 
    "type": "ScholarlyArticle", 
    "url": "https://link.springer.com/10.1007%2Fs12539-019-00323-0"
  }
]
 

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/s12539-019-00323-0'

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/s12539-019-00323-0'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/s12539-019-00323-0'

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

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/s12539-019-00323-0'


 

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

272 TRIPLES      21 PREDICATES      77 URIs      21 LITERALS      9 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/s12539-019-00323-0 schema:about anzsrc-for:08
2 anzsrc-for:0802
3 schema:author N6afd6785d5794dac9ead1c9be7aa1e77
4 schema:citation sg:pub.10.1007/978-3-642-13731-0_9
5 sg:pub.10.1007/978-981-10-5508-9_30
6 sg:pub.10.1007/s10618-017-0544-8
7 sg:pub.10.1007/s11103-005-8159-7
8 sg:pub.10.1038/nature11245
9 sg:pub.10.1038/nchembio.462
10 sg:pub.10.1038/nrg1272
11 sg:pub.10.1038/nrg2918
12 sg:pub.10.1140/epjb/e2004-00301-0
13 sg:pub.10.1186/1471-2105-12-45
14 sg:pub.10.1186/1471-2105-14-s7-s13
15 sg:pub.10.1891/0739-6686.29.55
16 https://doi.org/10.1002/wsbm.37
17 https://doi.org/10.1016/0004-3702(80)90051-x
18 https://doi.org/10.1016/0020-0255(79)90023-9
19 https://doi.org/10.1016/j.artint.2010.05.002
20 https://doi.org/10.1016/j.pharmthera.2013.01.016
21 https://doi.org/10.1049/iet-syb:20060071
22 https://doi.org/10.1073/pnas.2133841100
23 https://doi.org/10.1093/bfgp/els032
24 https://doi.org/10.1093/bfgp/els037
25 https://doi.org/10.1093/bioinformatics/btl301
26 https://doi.org/10.1093/bioinformatics/btw223
27 https://doi.org/10.1093/nar/gkj126
28 https://doi.org/10.1093/nar/gkq1039
29 https://doi.org/10.1093/nar/gks1094
30 https://doi.org/10.1093/nar/gkt1190
31 https://doi.org/10.1093/nar/gkw1102
32 https://doi.org/10.1109/tcbb.2016.2515595
33 https://doi.org/10.1109/tpami.2004.75
34 https://doi.org/10.1126/science.1073374
35 https://doi.org/10.1126/science.1091403
36 https://doi.org/10.1126/science.286.5439.509
37 https://doi.org/10.1126/science.298.5594.824
38 https://doi.org/10.1145/1081870.1081893
39 https://doi.org/10.1145/1671970.1921702
40 https://doi.org/10.1145/210332.210337
41 https://doi.org/10.12688/f1000research.4537.2
42 https://doi.org/10.1371/journal.pone.0076911
43 https://doi.org/10.1371/journal.pone.0098750
44 https://doi.org/10.14304/surya.jpr.v1n1.7
45 https://doi.org/10.14778/2535568.2448946
46 https://doi.org/10.3389/fbioe.2014.00069
47 https://doi.org/10.3389/fbioe.2015.00058
48 https://doi.org/10.3389/fgene.2014.00083
49 https://doi.org/10.3389/fgene.2014.00302
50 https://doi.org/10.4137/cin.s680
51 https://doi.org/10.5808/gi.2013.11.4.200
52 schema:datePublished 2019-03
53 schema:datePublishedReg 2019-03-01
54 schema:description Many scientific applications entail solving the subgraph isomorphism problem, i.e., given an input pattern graph, find all the subgraphs of a (usually much larger) target graph that are structurally equivalent to that input. Because subgraph isomorphism is NP-complete, methods to solve it have to use heuristics. This work evaluates subgraph isomorphism methods to assess their computational behavior on a wide range of synthetic and real graphs. Surprisingly, our experiments show that, among the leading algorithms, certain heuristics based only on pattern graphs are the most efficient.
55 schema:genre research_article
56 schema:inLanguage en
57 schema:isAccessibleForFree false
58 schema:isPartOf N222be54f739a40d18772dc8fca203e2b
59 N2b542a76b655435ea6615a8fa66bed8e
60 sg:journal.1042186
61 schema:name Fast Subgraph Matching Strategies Based on Pattern-Only Heuristics
62 schema:pagination 21-32
63 schema:productId N0582bec645d34a37b2af523bca3bc4e6
64 N3c15e0448e0547c38ecfafc23d0a45af
65 N482acd6fc3bb4070ac527290e4226a2c
66 Nb0973edf82d64e95b868d83aaa781744
67 Ne8c19c5fffc4441d9d0ccd0f6442b3dc
68 schema:sameAs https://app.dimensions.ai/details/publication/pub.1112283476
69 https://doi.org/10.1007/s12539-019-00323-0
70 schema:sdDatePublished 2019-04-11T11:24
71 schema:sdLicense https://scigraph.springernature.com/explorer/license/
72 schema:sdPublisher Nb5c10a6bf2f441e08e00707af68649f5
73 schema:url https://link.springer.com/10.1007%2Fs12539-019-00323-0
74 sgo:license sg:explorer/license/
75 sgo:sdDataset articles
76 rdf:type schema:ScholarlyArticle
77 N0582bec645d34a37b2af523bca3bc4e6 schema:name dimensions_id
78 schema:value pub.1112283476
79 rdf:type schema:PropertyValue
80 N089d7d2d83554e8c8a5d9218f7f7001a schema:affiliation https://www.grid.ac/institutes/grid.5611.3
81 schema:familyName Bonnici
82 schema:givenName Vincenzo
83 rdf:type schema:Person
84 N160942e6eef04ed1abbe35a4ae8578ac schema:affiliation https://www.grid.ac/institutes/grid.8158.4
85 schema:familyName Ferro
86 schema:givenName Alfredo
87 rdf:type schema:Person
88 N222be54f739a40d18772dc8fca203e2b schema:issueNumber 1
89 rdf:type schema:PublicationIssue
90 N2b542a76b655435ea6615a8fa66bed8e schema:volumeNumber 11
91 rdf:type schema:PublicationVolume
92 N3c15e0448e0547c38ecfafc23d0a45af schema:name readcube_id
93 schema:value 64faa2c4ce3d6c04b9d088d8c1cb813b622f074a5251563a3ed91b7c8b6f3ff7
94 rdf:type schema:PropertyValue
95 N463824cf90784d53ad62fe3251798d70 schema:affiliation https://www.grid.ac/institutes/grid.482020.c
96 schema:familyName Shasha
97 schema:givenName Dennis
98 rdf:type schema:Person
99 N47a36b7221154af59d56417bbda04cd6 rdf:first N7b824478a3c041cc9ad66478efb9c336
100 rdf:rest rdf:nil
101 N482acd6fc3bb4070ac527290e4226a2c schema:name nlm_unique_id
102 schema:value 101515919
103 rdf:type schema:PropertyValue
104 N6afd6785d5794dac9ead1c9be7aa1e77 rdf:first Nad657db2f777429b8413ea0c73a15f0c
105 rdf:rest Nb9c7a72e53bf4302a338e2979cd3bc9d
106 N7b824478a3c041cc9ad66478efb9c336 schema:affiliation https://www.grid.ac/institutes/grid.5611.3
107 schema:familyName Giugno
108 schema:givenName Rosalba
109 rdf:type schema:Person
110 N89124a8bca6d43feb7d9f026a5612c3d rdf:first N160942e6eef04ed1abbe35a4ae8578ac
111 rdf:rest Nc93cb362e2704ed59c8bcbdc0e9a87fd
112 N97a92184cfa74859b3e49deabd2da389 schema:affiliation https://www.grid.ac/institutes/grid.8158.4
113 schema:familyName Pulvirenti
114 schema:givenName Alfredo
115 rdf:type schema:Person
116 Nad657db2f777429b8413ea0c73a15f0c schema:affiliation https://www.grid.ac/institutes/grid.5611.3
117 schema:familyName Aparo
118 schema:givenName Antonino
119 rdf:type schema:Person
120 Nb0973edf82d64e95b868d83aaa781744 schema:name pubmed_id
121 schema:value 30790228
122 rdf:type schema:PropertyValue
123 Nb1f69d023928436ca2bbd766c02001de rdf:first N97a92184cfa74859b3e49deabd2da389
124 rdf:rest N47a36b7221154af59d56417bbda04cd6
125 Nb5c10a6bf2f441e08e00707af68649f5 schema:name Springer Nature - SN SciGraph project
126 rdf:type schema:Organization
127 Nb9c7a72e53bf4302a338e2979cd3bc9d rdf:first N089d7d2d83554e8c8a5d9218f7f7001a
128 rdf:rest Ndd38455fc3594b548bec92b6a6b814bb
129 Nc366f02680194be3a68c6fdb934a519c schema:affiliation https://www.grid.ac/institutes/grid.8158.4
130 schema:familyName Micale
131 schema:givenName Giovanni
132 rdf:type schema:Person
133 Nc93cb362e2704ed59c8bcbdc0e9a87fd rdf:first N463824cf90784d53ad62fe3251798d70
134 rdf:rest Nb1f69d023928436ca2bbd766c02001de
135 Ndd38455fc3594b548bec92b6a6b814bb rdf:first Nc366f02680194be3a68c6fdb934a519c
136 rdf:rest N89124a8bca6d43feb7d9f026a5612c3d
137 Ne8c19c5fffc4441d9d0ccd0f6442b3dc schema:name doi
138 schema:value 10.1007/s12539-019-00323-0
139 rdf:type schema:PropertyValue
140 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
141 schema:name Information and Computing Sciences
142 rdf:type schema:DefinedTerm
143 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
144 schema:name Computation Theory and Mathematics
145 rdf:type schema:DefinedTerm
146 sg:grant.3135072 http://pending.schema.org/fundedItem sg:pub.10.1007/s12539-019-00323-0
147 rdf:type schema:MonetaryGrant
148 sg:grant.3580241 http://pending.schema.org/fundedItem sg:pub.10.1007/s12539-019-00323-0
149 rdf:type schema:MonetaryGrant
150 sg:grant.3848075 http://pending.schema.org/fundedItem sg:pub.10.1007/s12539-019-00323-0
151 rdf:type schema:MonetaryGrant
152 sg:journal.1042186 schema:issn 1867-1462
153 1913-2751
154 schema:name Interdisciplinary Sciences: Computational Life Sciences
155 rdf:type schema:Periodical
156 sg:pub.10.1007/978-3-642-13731-0_9 schema:sameAs https://app.dimensions.ai/details/publication/pub.1013527218
157 https://doi.org/10.1007/978-3-642-13731-0_9
158 rdf:type schema:CreativeWork
159 sg:pub.10.1007/978-981-10-5508-9_30 schema:sameAs https://app.dimensions.ai/details/publication/pub.1092166189
160 https://doi.org/10.1007/978-981-10-5508-9_30
161 rdf:type schema:CreativeWork
162 sg:pub.10.1007/s10618-017-0544-8 schema:sameAs https://app.dimensions.ai/details/publication/pub.1092500787
163 https://doi.org/10.1007/s10618-017-0544-8
164 rdf:type schema:CreativeWork
165 sg:pub.10.1007/s11103-005-8159-7 schema:sameAs https://app.dimensions.ai/details/publication/pub.1028739512
166 https://doi.org/10.1007/s11103-005-8159-7
167 rdf:type schema:CreativeWork
168 sg:pub.10.1038/nature11245 schema:sameAs https://app.dimensions.ai/details/publication/pub.1028790868
169 https://doi.org/10.1038/nature11245
170 rdf:type schema:CreativeWork
171 sg:pub.10.1038/nchembio.462 schema:sameAs https://app.dimensions.ai/details/publication/pub.1020048109
172 https://doi.org/10.1038/nchembio.462
173 rdf:type schema:CreativeWork
174 sg:pub.10.1038/nrg1272 schema:sameAs https://app.dimensions.ai/details/publication/pub.1018231980
175 https://doi.org/10.1038/nrg1272
176 rdf:type schema:CreativeWork
177 sg:pub.10.1038/nrg2918 schema:sameAs https://app.dimensions.ai/details/publication/pub.1021371713
178 https://doi.org/10.1038/nrg2918
179 rdf:type schema:CreativeWork
180 sg:pub.10.1140/epjb/e2004-00301-0 schema:sameAs https://app.dimensions.ai/details/publication/pub.1045239815
181 https://doi.org/10.1140/epjb/e2004-00301-0
182 rdf:type schema:CreativeWork
183 sg:pub.10.1186/1471-2105-12-45 schema:sameAs https://app.dimensions.ai/details/publication/pub.1039226122
184 https://doi.org/10.1186/1471-2105-12-45
185 rdf:type schema:CreativeWork
186 sg:pub.10.1186/1471-2105-14-s7-s13 schema:sameAs https://app.dimensions.ai/details/publication/pub.1028830970
187 https://doi.org/10.1186/1471-2105-14-s7-s13
188 rdf:type schema:CreativeWork
189 sg:pub.10.1891/0739-6686.29.55 schema:sameAs https://app.dimensions.ai/details/publication/pub.1005609973
190 https://doi.org/10.1891/0739-6686.29.55
191 rdf:type schema:CreativeWork
192 https://doi.org/10.1002/wsbm.37 schema:sameAs https://app.dimensions.ai/details/publication/pub.1009562848
193 rdf:type schema:CreativeWork
194 https://doi.org/10.1016/0004-3702(80)90051-x schema:sameAs https://app.dimensions.ai/details/publication/pub.1045789426
195 rdf:type schema:CreativeWork
196 https://doi.org/10.1016/0020-0255(79)90023-9 schema:sameAs https://app.dimensions.ai/details/publication/pub.1036030687
197 rdf:type schema:CreativeWork
198 https://doi.org/10.1016/j.artint.2010.05.002 schema:sameAs https://app.dimensions.ai/details/publication/pub.1039626128
199 rdf:type schema:CreativeWork
200 https://doi.org/10.1016/j.pharmthera.2013.01.016 schema:sameAs https://app.dimensions.ai/details/publication/pub.1036857532
201 rdf:type schema:CreativeWork
202 https://doi.org/10.1049/iet-syb:20060071 schema:sameAs https://app.dimensions.ai/details/publication/pub.1056839183
203 rdf:type schema:CreativeWork
204 https://doi.org/10.1073/pnas.2133841100 schema:sameAs https://app.dimensions.ai/details/publication/pub.1023151304
205 rdf:type schema:CreativeWork
206 https://doi.org/10.1093/bfgp/els032 schema:sameAs https://app.dimensions.ai/details/publication/pub.1016403562
207 rdf:type schema:CreativeWork
208 https://doi.org/10.1093/bfgp/els037 schema:sameAs https://app.dimensions.ai/details/publication/pub.1033002789
209 rdf:type schema:CreativeWork
210 https://doi.org/10.1093/bioinformatics/btl301 schema:sameAs https://app.dimensions.ai/details/publication/pub.1010804001
211 rdf:type schema:CreativeWork
212 https://doi.org/10.1093/bioinformatics/btw223 schema:sameAs https://app.dimensions.ai/details/publication/pub.1059414750
213 rdf:type schema:CreativeWork
214 https://doi.org/10.1093/nar/gkj126 schema:sameAs https://app.dimensions.ai/details/publication/pub.1049555345
215 rdf:type schema:CreativeWork
216 https://doi.org/10.1093/nar/gkq1039 schema:sameAs https://app.dimensions.ai/details/publication/pub.1026557089
217 rdf:type schema:CreativeWork
218 https://doi.org/10.1093/nar/gks1094 schema:sameAs https://app.dimensions.ai/details/publication/pub.1045624288
219 rdf:type schema:CreativeWork
220 https://doi.org/10.1093/nar/gkt1190 schema:sameAs https://app.dimensions.ai/details/publication/pub.1039838368
221 rdf:type schema:CreativeWork
222 https://doi.org/10.1093/nar/gkw1102 schema:sameAs https://app.dimensions.ai/details/publication/pub.1041939167
223 rdf:type schema:CreativeWork
224 https://doi.org/10.1109/tcbb.2016.2515595 schema:sameAs https://app.dimensions.ai/details/publication/pub.1061541576
225 rdf:type schema:CreativeWork
226 https://doi.org/10.1109/tpami.2004.75 schema:sameAs https://app.dimensions.ai/details/publication/pub.1061742753
227 rdf:type schema:CreativeWork
228 https://doi.org/10.1126/science.1073374 schema:sameAs https://app.dimensions.ai/details/publication/pub.1019781582
229 rdf:type schema:CreativeWork
230 https://doi.org/10.1126/science.1091403 schema:sameAs https://app.dimensions.ai/details/publication/pub.1015172314
231 rdf:type schema:CreativeWork
232 https://doi.org/10.1126/science.286.5439.509 schema:sameAs https://app.dimensions.ai/details/publication/pub.1010080128
233 rdf:type schema:CreativeWork
234 https://doi.org/10.1126/science.298.5594.824 schema:sameAs https://app.dimensions.ai/details/publication/pub.1033238539
235 rdf:type schema:CreativeWork
236 https://doi.org/10.1145/1081870.1081893 schema:sameAs https://app.dimensions.ai/details/publication/pub.1020085889
237 rdf:type schema:CreativeWork
238 https://doi.org/10.1145/1671970.1921702 schema:sameAs https://app.dimensions.ai/details/publication/pub.1014512066
239 rdf:type schema:CreativeWork
240 https://doi.org/10.1145/210332.210337 schema:sameAs https://app.dimensions.ai/details/publication/pub.1011509889
241 rdf:type schema:CreativeWork
242 https://doi.org/10.12688/f1000research.4537.2 schema:sameAs https://app.dimensions.ai/details/publication/pub.1007578244
243 rdf:type schema:CreativeWork
244 https://doi.org/10.1371/journal.pone.0076911 schema:sameAs https://app.dimensions.ai/details/publication/pub.1024443802
245 rdf:type schema:CreativeWork
246 https://doi.org/10.1371/journal.pone.0098750 schema:sameAs https://app.dimensions.ai/details/publication/pub.1008955663
247 rdf:type schema:CreativeWork
248 https://doi.org/10.14304/surya.jpr.v1n1.7 schema:sameAs https://app.dimensions.ai/details/publication/pub.1067261424
249 rdf:type schema:CreativeWork
250 https://doi.org/10.14778/2535568.2448946 schema:sameAs https://app.dimensions.ai/details/publication/pub.1067368130
251 rdf:type schema:CreativeWork
252 https://doi.org/10.3389/fbioe.2014.00069 schema:sameAs https://app.dimensions.ai/details/publication/pub.1050267577
253 rdf:type schema:CreativeWork
254 https://doi.org/10.3389/fbioe.2015.00058 schema:sameAs https://app.dimensions.ai/details/publication/pub.1010674371
255 rdf:type schema:CreativeWork
256 https://doi.org/10.3389/fgene.2014.00083 schema:sameAs https://app.dimensions.ai/details/publication/pub.1022436615
257 rdf:type schema:CreativeWork
258 https://doi.org/10.3389/fgene.2014.00302 schema:sameAs https://app.dimensions.ai/details/publication/pub.1013885289
259 rdf:type schema:CreativeWork
260 https://doi.org/10.4137/cin.s680 schema:sameAs https://app.dimensions.ai/details/publication/pub.1077858174
261 rdf:type schema:CreativeWork
262 https://doi.org/10.5808/gi.2013.11.4.200 schema:sameAs https://app.dimensions.ai/details/publication/pub.1030838547
263 rdf:type schema:CreativeWork
264 https://www.grid.ac/institutes/grid.482020.c schema:alternateName Courant Institute of Mathematical Sciences
265 schema:name Computer Science Department, Courant Institute, New York University, New York, USA
266 rdf:type schema:Organization
267 https://www.grid.ac/institutes/grid.5611.3 schema:alternateName University of Verona
268 schema:name Department of Computer Science, University of Verona, Verona, Italy
269 rdf:type schema:Organization
270 https://www.grid.ac/institutes/grid.8158.4 schema:alternateName University of Catania
271 schema:name Department of Clinical and Experimental Medicine, University of Catania, Catania, Italy
272 rdf:type schema:Organization
 




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


...