Ontology type: schema:Chapter Open Access: True
2005
AUTHORSW. Henry Suters , Faisal N. Abu-Khzam , Yun Zhang , Christopher T. Symons , Nagiza F. Samatova , Michael A. Langston
ABSTRACTThe Maximum Common Subgraph (MCS) problem appears in many guises and in a wide variety of applications. The usual goal is to take as inputs two graphs, of order m and n, respectively, and find the largest induced subgraph contained in both of them. MCS is frequently solved by reduction to the problem of finding a maximum clique in the order mn association graph, which is a particular form of product graph built from the inputs. In this paper a new algorithm, termed “clique branching,” is proposed that exploits a special structure inherent in the association graph. This structure contains a large number of naturally-ordered cliques that are present in the association graph’s complement. A detailed analysis shows that the proposed algorithm requires O((m+1)n) time, which is a superior worst-case bound to those known for previously-analyzed algorithms in the setting of the MCS problem. More... »
PAGES717-727
Computing and Combinatorics
ISBN
978-3-540-28061-3
978-3-540-31806-4
http://scigraph.springernature.com/pub.10.1007/11533719_73
DOIhttp://dx.doi.org/10.1007/11533719_73
DIMENSIONShttps://app.dimensions.ai/details/publication/pub.1017311354
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": "Carson Newman College",
"id": "https://www.grid.ac/institutes/grid.432998.d",
"name": [
"Department of Mathematics and Computer Science, Carson-Newman College, CN Box 71958, 37760, Jefferson City, TN, USA"
],
"type": "Organization"
},
"familyName": "Suters",
"givenName": "W. Henry",
"id": "sg:person.07512420001.13",
"sameAs": [
"https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07512420001.13"
],
"type": "Person"
},
{
"affiliation": {
"alternateName": "Lebanese American University",
"id": "https://www.grid.ac/institutes/grid.411323.6",
"name": [
"Division of Computer Science and Mathematics, Lebanese American University, Beirut, Lebanon"
],
"type": "Organization"
},
"familyName": "Abu-Khzam",
"givenName": "Faisal N.",
"id": "sg:person.010673015605.56",
"sameAs": [
"https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010673015605.56"
],
"type": "Person"
},
{
"affiliation": {
"alternateName": "University of Tennessee at Knoxville",
"id": "https://www.grid.ac/institutes/grid.411461.7",
"name": [
"Department of Computer Science, University of Tennessee, 37996 3450, Knoxville, TN, USA"
],
"type": "Organization"
},
"familyName": "Zhang",
"givenName": "Yun",
"id": "sg:person.01012445310.23",
"sameAs": [
"https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01012445310.23"
],
"type": "Person"
},
{
"affiliation": {
"alternateName": "Oak Ridge National Laboratory",
"id": "https://www.grid.ac/institutes/grid.135519.a",
"name": [
"Computer Science and Mathematics Division, Oak Ridge National Laboratory, P.O. Box 2008, 37831 6367, Oak Ridge, TN, USA"
],
"type": "Organization"
},
"familyName": "Symons",
"givenName": "Christopher T.",
"id": "sg:person.07460765211.69",
"sameAs": [
"https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07460765211.69"
],
"type": "Person"
},
{
"affiliation": {
"alternateName": "Oak Ridge National Laboratory",
"id": "https://www.grid.ac/institutes/grid.135519.a",
"name": [
"Computer Science and Mathematics Division, Oak Ridge National Laboratory, P.O. Box 2008, 37831 6367, Oak Ridge, TN, USA"
],
"type": "Organization"
},
"familyName": "Samatova",
"givenName": "Nagiza F.",
"id": "sg:person.01360475442.35",
"sameAs": [
"https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01360475442.35"
],
"type": "Person"
},
{
"affiliation": {
"alternateName": "University of Tennessee at Knoxville",
"id": "https://www.grid.ac/institutes/grid.411461.7",
"name": [
"Department of Computer Science, University of Tennessee, 37996 3450, Knoxville, TN, USA"
],
"type": "Organization"
},
"familyName": "Langston",
"givenName": "Michael A.",
"id": "sg:person.01102314053.86",
"sameAs": [
"https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01102314053.86"
],
"type": "Person"
}
],
"citation": [
{
"id": "https://doi.org/10.1016/s0167-8655(02)00256-8",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1002178641"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1016/s0167-8655(02)00256-8",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1002178641"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1016/s0304-3975(00)00286-3",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1002396737"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1023/a:1021271615909",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1013172110",
"https://doi.org/10.1023/a:1021271615909"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/3-540-45028-9_12",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1015430865",
"https://doi.org/10.1007/3-540-45028-9_12"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/3-540-45028-9_12",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1015430865",
"https://doi.org/10.1007/3-540-45028-9_12"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1016/j.ipl.2004.06.019",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1015444365"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/978-1-4757-3023-4_1",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1027732500",
"https://doi.org/10.1007/978-1-4757-3023-4_1"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1002/spe.588",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1027808390"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/3-540-70659-3_12",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1029153321",
"https://doi.org/10.1007/3-540-70659-3_12"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1016/s0031-3203(00)00048-0",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1032001799"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1002/spe.4380120103",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1039746604"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/3-540-55210-3_198",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1040657953",
"https://doi.org/10.1007/3-540-55210-3_198"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/bf02575586",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1041808659",
"https://doi.org/10.1007/bf02575586"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/bf02575586",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1041808659",
"https://doi.org/10.1007/bf02575586"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1145/362342.362367",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1049082651"
],
"type": "CreativeWork"
},
{
"id": "https://app.dimensions.ai/details/publication/pub.1050354225",
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/978-1-4612-0515-9",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1050354225",
"https://doi.org/10.1007/978-1-4612-0515-9"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/978-1-4612-0515-9",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1050354225",
"https://doi.org/10.1007/978-1-4612-0515-9"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1021/ci00031a005",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1055400530"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1142/s0218001404003228",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1062949422"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1109/aiccsa.2005.1387015",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1093379169"
],
"type": "CreativeWork"
}
],
"datePublished": "2005",
"datePublishedReg": "2005-01-01",
"description": "The Maximum Common Subgraph (MCS) problem appears in many guises and in a wide variety of applications. The usual goal is to take as inputs two graphs, of order m and n, respectively, and find the largest induced subgraph contained in both of them. MCS is frequently solved by reduction to the problem of finding a maximum clique in the order mn association graph, which is a particular form of product graph built from the inputs. In this paper a new algorithm, termed \u201cclique branching,\u201d is proposed that exploits a special structure inherent in the association graph. This structure contains a large number of naturally-ordered cliques that are present in the association graph\u2019s complement. A detailed analysis shows that the proposed algorithm requires O((m+1)n) time, which is a superior worst-case bound to those known for previously-analyzed algorithms in the setting of the MCS problem.",
"editor": [
{
"familyName": "Wang",
"givenName": "Lusheng",
"type": "Person"
}
],
"genre": "chapter",
"id": "sg:pub.10.1007/11533719_73",
"inLanguage": [
"en"
],
"isAccessibleForFree": true,
"isPartOf": {
"isbn": [
"978-3-540-28061-3",
"978-3-540-31806-4"
],
"name": "Computing and Combinatorics",
"type": "Book"
},
"name": "A New Approach and Faster Exact Methods for the Maximum Common Subgraph Problem",
"pagination": "717-727",
"productId": [
{
"name": "dimensions_id",
"type": "PropertyValue",
"value": [
"pub.1017311354"
]
},
{
"name": "doi",
"type": "PropertyValue",
"value": [
"10.1007/11533719_73"
]
},
{
"name": "readcube_id",
"type": "PropertyValue",
"value": [
"527a7c328d47b1136ba6decf4aff31417c8b8496584176951f74c368b1bea038"
]
}
],
"publisher": {
"location": "Berlin, Heidelberg",
"name": "Springer Berlin Heidelberg",
"type": "Organisation"
},
"sameAs": [
"https://doi.org/10.1007/11533719_73",
"https://app.dimensions.ai/details/publication/pub.1017311354"
],
"sdDataset": "chapters",
"sdDatePublished": "2019-04-16T08: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/0000000363_0000000363/records_70046_00000000.jsonl",
"type": "Chapter",
"url": "https://link.springer.com/10.1007%2F11533719_73"
}
]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/11533719_73'
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/11533719_73'
Turtle is a human-readable linked data format.
curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/11533719_73'
RDF/XML is a standard XML format for linked data.
curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/11533719_73'
This table displays all metadata directly associated to this object as RDF triples.
169 TRIPLES
23 PREDICATES
45 URIs
20 LITERALS
8 BLANK NODES