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

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 Nbf9828ccd6964a64aebbbc821730a9a8
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 N4ea30d37c26644cd92602c2eb2213da4
59 Nfc33f031dc4d45549892d48b7c6aad6c
60 sg:journal.1042186
61 schema:name Fast Subgraph Matching Strategies Based on Pattern-Only Heuristics
62 schema:pagination 21-32
63 schema:productId N2f9d5c1d50aa4aecb2bb64a616461b89
64 N6cdc1a79ee414d9b850be7b874cbc7d7
65 N727edd03073b436eb633045983c17852
66 N838bb0c011834b4f881f33418cb35fdc
67 Nf1193fb7ed0f4ad6b9036488b363aac3
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 Ncf34489c1d9d471eb3b0412481c2585e
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 N0aff5f3de17343fa8254de4cd74e64fb schema:affiliation https://www.grid.ac/institutes/grid.8158.4
78 schema:familyName Pulvirenti
79 schema:givenName Alfredo
80 rdf:type schema:Person
81 N237167f3bdbe4a49b395e361d3531780 rdf:first N7ff465068cea49f1820fbe7fdd8229d1
82 rdf:rest Nf7392bb9ed49483f8b65cd59a900b30c
83 N2f9d5c1d50aa4aecb2bb64a616461b89 schema:name doi
84 schema:value 10.1007/s12539-019-00323-0
85 rdf:type schema:PropertyValue
86 N34fa6c752bac4269adc7cd446ea09d21 schema:affiliation https://www.grid.ac/institutes/grid.5611.3
87 schema:familyName Bonnici
88 schema:givenName Vincenzo
89 rdf:type schema:Person
90 N364cd7e6178e46bebbc2cf5ddc2d99b9 rdf:first N34fa6c752bac4269adc7cd446ea09d21
91 rdf:rest Ne93c65cdcd34449eb2ef41a5fb8fad8b
92 N4ea30d37c26644cd92602c2eb2213da4 schema:issueNumber 1
93 rdf:type schema:PublicationIssue
94 N6cdc1a79ee414d9b850be7b874cbc7d7 schema:name pubmed_id
95 schema:value 30790228
96 rdf:type schema:PropertyValue
97 N727edd03073b436eb633045983c17852 schema:name readcube_id
98 schema:value 64faa2c4ce3d6c04b9d088d8c1cb813b622f074a5251563a3ed91b7c8b6f3ff7
99 rdf:type schema:PropertyValue
100 N7fcc4f13754549c983e9147f77788381 schema:affiliation https://www.grid.ac/institutes/grid.8158.4
101 schema:familyName Micale
102 schema:givenName Giovanni
103 rdf:type schema:Person
104 N7ff465068cea49f1820fbe7fdd8229d1 schema:affiliation https://www.grid.ac/institutes/grid.8158.4
105 schema:familyName Ferro
106 schema:givenName Alfredo
107 rdf:type schema:Person
108 N838bb0c011834b4f881f33418cb35fdc schema:name nlm_unique_id
109 schema:value 101515919
110 rdf:type schema:PropertyValue
111 N8f98a030e9e04e9cb1d0f399310642ff schema:affiliation https://www.grid.ac/institutes/grid.5611.3
112 schema:familyName Giugno
113 schema:givenName Rosalba
114 rdf:type schema:Person
115 Nabb9eba535ae4754a0821c27b57a6929 rdf:first N0aff5f3de17343fa8254de4cd74e64fb
116 rdf:rest Ncbc7140819fe44b784f04a5536f6d18b
117 Nbf9828ccd6964a64aebbbc821730a9a8 rdf:first Ne3a3b50b79e24b1c8e50d693ee554b7d
118 rdf:rest N364cd7e6178e46bebbc2cf5ddc2d99b9
119 Nc6e9fd7065f14222aa0c2b8d3761e4ee schema:affiliation https://www.grid.ac/institutes/grid.482020.c
120 schema:familyName Shasha
121 schema:givenName Dennis
122 rdf:type schema:Person
123 Ncbc7140819fe44b784f04a5536f6d18b rdf:first N8f98a030e9e04e9cb1d0f399310642ff
124 rdf:rest rdf:nil
125 Ncf34489c1d9d471eb3b0412481c2585e schema:name Springer Nature - SN SciGraph project
126 rdf:type schema:Organization
127 Ne3a3b50b79e24b1c8e50d693ee554b7d schema:affiliation https://www.grid.ac/institutes/grid.5611.3
128 schema:familyName Aparo
129 schema:givenName Antonino
130 rdf:type schema:Person
131 Ne93c65cdcd34449eb2ef41a5fb8fad8b rdf:first N7fcc4f13754549c983e9147f77788381
132 rdf:rest N237167f3bdbe4a49b395e361d3531780
133 Nf1193fb7ed0f4ad6b9036488b363aac3 schema:name dimensions_id
134 schema:value pub.1112283476
135 rdf:type schema:PropertyValue
136 Nf7392bb9ed49483f8b65cd59a900b30c rdf:first Nc6e9fd7065f14222aa0c2b8d3761e4ee
137 rdf:rest Nabb9eba535ae4754a0821c27b57a6929
138 Nfc33f031dc4d45549892d48b7c6aad6c schema:volumeNumber 11
139 rdf:type schema:PublicationVolume
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)


...