On the approximability of the maximum common subgraph problem View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

1992

AUTHORS

Viggo Kann

ABSTRACT

Some versions of the maximum common subgraph problem are studied and approximation algorithms are given. The maximum bounded common induced subgraph problem is shown to be Max SNP-hard and the maximum unbounded common induced subgraph problem is shown to be as hard to approximate as the maximum independent set problem. The maximum common induced connected subgraph problem is still harder to approximate and is shown to be NPO PB-complete, i.e. complete in the class of optimization problems with optimal value bounded by a polynomial. More... »

PAGES

375-388

Book

TITLE

STACS 92

ISBN

978-3-540-55210-9
978-3-540-46775-5

Author Affiliations

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/3-540-55210-3_198

DOI

http://dx.doi.org/10.1007/3-540-55210-3_198

DIMENSIONS

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


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/0103", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Numerical and Computational Mathematics", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/01", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Mathematical Sciences", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Royal Institute of Technology", 
          "id": "https://www.grid.ac/institutes/grid.5037.1", 
          "name": [
            "Department of Numerical Analysis and Computing Science, Royal Institute of Technology, S-100 44\u00a0Stockholm, Sweden"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Kann", 
        "givenName": "Viggo", 
        "id": "sg:person.014343100201.33", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014343100201.33"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "1992", 
    "datePublishedReg": "1992-01-01", 
    "description": "Some versions of the maximum common subgraph problem are studied and approximation algorithms are given. The maximum bounded common induced subgraph problem is shown to be Max SNP-hard and the maximum unbounded common induced subgraph problem is shown to be as hard to approximate as the maximum independent set problem. The maximum common induced connected subgraph problem is still harder to approximate and is shown to be NPO PB-complete, i.e. complete in the class of optimization problems with optimal value bounded by a polynomial.", 
    "editor": [
      {
        "familyName": "Finkel", 
        "givenName": "Alain", 
        "type": "Person"
      }, 
      {
        "familyName": "Jantzen", 
        "givenName": "Matthias", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/3-540-55210-3_198", 
    "inLanguage": [
      "en"
    ], 
    "isAccessibleForFree": true, 
    "isPartOf": {
      "isbn": [
        "978-3-540-55210-9", 
        "978-3-540-46775-5"
      ], 
      "name": "STACS 92", 
      "type": "Book"
    }, 
    "name": "On the approximability of the maximum common subgraph problem", 
    "pagination": "375-388", 
    "productId": [
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/3-540-55210-3_198"
        ]
      }, 
      {
        "name": "readcube_id", 
        "type": "PropertyValue", 
        "value": [
          "c1adb4d977eb90f6ce45d65886c122ba480284236981e8199a097f7c936ec825"
        ]
      }, 
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1040657953"
        ]
      }
    ], 
    "publisher": {
      "location": "Berlin, Heidelberg", 
      "name": "Springer Berlin Heidelberg", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/3-540-55210-3_198", 
      "https://app.dimensions.ai/details/publication/pub.1040657953"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2019-04-15T21:47", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-uberresearch-data-dimensions-target-20181106-alternative/cleanup/v134/2549eaecd7973599484d7c17b260dba0a4ecb94b/merge/v9/a6c9fde33151104705d4d7ff012ea9563521a3ce/jats-lookup/v90/0000000001_0000000264/records_8693_00000070.jsonl", 
    "type": "Chapter", 
    "url": "http://link.springer.com/10.1007/3-540-55210-3_198"
  }
]
 

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/3-540-55210-3_198'

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/3-540-55210-3_198'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/3-540-55210-3_198'

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

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/3-540-55210-3_198'


 

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

70 TRIPLES      22 PREDICATES      27 URIs      20 LITERALS      8 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/3-540-55210-3_198 schema:about anzsrc-for:01
2 anzsrc-for:0103
3 schema:author N3936f357e65c4c0999c9c75600b345e2
4 schema:datePublished 1992
5 schema:datePublishedReg 1992-01-01
6 schema:description Some versions of the maximum common subgraph problem are studied and approximation algorithms are given. The maximum bounded common induced subgraph problem is shown to be Max SNP-hard and the maximum unbounded common induced subgraph problem is shown to be as hard to approximate as the maximum independent set problem. The maximum common induced connected subgraph problem is still harder to approximate and is shown to be NPO PB-complete, i.e. complete in the class of optimization problems with optimal value bounded by a polynomial.
7 schema:editor N89770b6de2184c8499a8e5ca9c315e93
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree true
11 schema:isPartOf N782ea82ab74243628fce404f95e39882
12 schema:name On the approximability of the maximum common subgraph problem
13 schema:pagination 375-388
14 schema:productId N06ac742374ae4e30870e12102cf49780
15 N2edf7170ac974255953a79866c09b64a
16 Ne8619ad4fafa473baa49919c5f9f9899
17 schema:publisher N46d094bce77b4c0888ee9e6b2c9cda67
18 schema:sameAs https://app.dimensions.ai/details/publication/pub.1040657953
19 https://doi.org/10.1007/3-540-55210-3_198
20 schema:sdDatePublished 2019-04-15T21:47
21 schema:sdLicense https://scigraph.springernature.com/explorer/license/
22 schema:sdPublisher Nf4a76788509f401a927503ec7720ad1b
23 schema:url http://link.springer.com/10.1007/3-540-55210-3_198
24 sgo:license sg:explorer/license/
25 sgo:sdDataset chapters
26 rdf:type schema:Chapter
27 N06ac742374ae4e30870e12102cf49780 schema:name doi
28 schema:value 10.1007/3-540-55210-3_198
29 rdf:type schema:PropertyValue
30 N2edf7170ac974255953a79866c09b64a schema:name readcube_id
31 schema:value c1adb4d977eb90f6ce45d65886c122ba480284236981e8199a097f7c936ec825
32 rdf:type schema:PropertyValue
33 N3936f357e65c4c0999c9c75600b345e2 rdf:first sg:person.014343100201.33
34 rdf:rest rdf:nil
35 N46d094bce77b4c0888ee9e6b2c9cda67 schema:location Berlin, Heidelberg
36 schema:name Springer Berlin Heidelberg
37 rdf:type schema:Organisation
38 N4bc7ded4db204aaf9688cbbd95e10d2e rdf:first N502283ca906c4249b4dcf6efa2667620
39 rdf:rest rdf:nil
40 N502283ca906c4249b4dcf6efa2667620 schema:familyName Jantzen
41 schema:givenName Matthias
42 rdf:type schema:Person
43 N782ea82ab74243628fce404f95e39882 schema:isbn 978-3-540-46775-5
44 978-3-540-55210-9
45 schema:name STACS 92
46 rdf:type schema:Book
47 N89770b6de2184c8499a8e5ca9c315e93 rdf:first Nd04bff5fdb374e4e8527264bd7507133
48 rdf:rest N4bc7ded4db204aaf9688cbbd95e10d2e
49 Nd04bff5fdb374e4e8527264bd7507133 schema:familyName Finkel
50 schema:givenName Alain
51 rdf:type schema:Person
52 Ne8619ad4fafa473baa49919c5f9f9899 schema:name dimensions_id
53 schema:value pub.1040657953
54 rdf:type schema:PropertyValue
55 Nf4a76788509f401a927503ec7720ad1b schema:name Springer Nature - SN SciGraph project
56 rdf:type schema:Organization
57 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
58 schema:name Mathematical Sciences
59 rdf:type schema:DefinedTerm
60 anzsrc-for:0103 schema:inDefinedTermSet anzsrc-for:
61 schema:name Numerical and Computational Mathematics
62 rdf:type schema:DefinedTerm
63 sg:person.014343100201.33 schema:affiliation https://www.grid.ac/institutes/grid.5037.1
64 schema:familyName Kann
65 schema:givenName Viggo
66 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014343100201.33
67 rdf:type schema:Person
68 https://www.grid.ac/institutes/grid.5037.1 schema:alternateName Royal Institute of Technology
69 schema:name Department of Numerical Analysis and Computing Science, Royal Institute of Technology, S-100 44 Stockholm, Sweden
70 rdf:type schema:Organization
 




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


...