Ontology type: schema:ScholarlyArticle
2019-03
AUTHORSAntonino Aparo, Vincenzo Bonnici, Giovanni Micale, Alfredo Ferro, Dennis Shasha, Alfredo Pulvirenti, Rosalba Giugno
ABSTRACTMany 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... »
PAGES21-32
http://scigraph.springernature.com/pub.10.1007/s12539-019-00323-0
DOIhttp://dx.doi.org/10.1007/s12539-019-00323-0
DIMENSIONShttps://app.dimensions.ai/details/publication/pub.1112283476
PUBMEDhttps://www.ncbi.nlm.nih.gov/pubmed/30790228
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
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