Hardness of approximating problems on cubic graphs View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

1997

AUTHORS

Paola Alimonti , Viggo Kann

ABSTRACT

Four fundamental graph problems, Minimum vertex cover, Maximum independent set, Minimum dominating set and Maximum cut, are shown to be APX-complete even for cubic graphs. This means that unless P=NP these problems do not admit any polynomial time approximation scheme on input graphs of degree bounded by three.

PAGES

288-298

Book

TITLE

Algorithms and Complexity

ISBN

978-3-540-62592-6
978-3-540-68323-0

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/3-540-62592-5_80

DOI

http://dx.doi.org/10.1007/3-540-62592-5_80

DIMENSIONS

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


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": "Sapienza University of Rome", 
          "id": "https://www.grid.ac/institutes/grid.7841.a", 
          "name": [
            "Dip. Informatics Sistemistica, University of Rome \u201cla Sapienza\u201d, Via Salaria 113, 00198\u00a0Rome, Italy"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Alimonti", 
        "givenName": "Paola", 
        "id": "sg:person.015632520461.69", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015632520461.69"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Royal Institute of Technology", 
          "id": "https://www.grid.ac/institutes/grid.5037.1", 
          "name": [
            "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": "1997", 
    "datePublishedReg": "1997-01-01", 
    "description": "Four fundamental graph problems, Minimum vertex cover, Maximum independent set, Minimum dominating set and Maximum cut, are shown to be APX-complete even for cubic graphs. This means that unless P=NP these problems do not admit any polynomial time approximation scheme on input graphs of degree bounded by three.", 
    "editor": [
      {
        "familyName": "Bongiovanni", 
        "givenName": "Giancarlo", 
        "type": "Person"
      }, 
      {
        "familyName": "Bovet", 
        "givenName": "Daniel Pierre", 
        "type": "Person"
      }, 
      {
        "familyName": "Battista", 
        "givenName": "Giuseppe", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/3-540-62592-5_80", 
    "inLanguage": [
      "en"
    ], 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-540-62592-6", 
        "978-3-540-68323-0"
      ], 
      "name": "Algorithms and Complexity", 
      "type": "Book"
    }, 
    "name": "Hardness of approximating problems on cubic graphs", 
    "pagination": "288-298", 
    "productId": [
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/3-540-62592-5_80"
        ]
      }, 
      {
        "name": "readcube_id", 
        "type": "PropertyValue", 
        "value": [
          "c9503066fae9e82ce016cb4bb15c499186e473d218d19b0ada57d2170315a311"
        ]
      }, 
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1042261594"
        ]
      }
    ], 
    "publisher": {
      "location": "Berlin, Heidelberg", 
      "name": "Springer Berlin Heidelberg", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/3-540-62592-5_80", 
      "https://app.dimensions.ai/details/publication/pub.1042261594"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2019-04-15T11:23", 
    "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_8660_00000072.jsonl", 
    "type": "Chapter", 
    "url": "http://link.springer.com/10.1007/3-540-62592-5_80"
  }
]
 

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-62592-5_80'

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-62592-5_80'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/3-540-62592-5_80'

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-62592-5_80'


 

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

85 TRIPLES      22 PREDICATES      27 URIs      20 LITERALS      8 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/3-540-62592-5_80 schema:about anzsrc-for:08
2 anzsrc-for:0802
3 schema:author N44cb91d29c56420daf4f5e330a356691
4 schema:datePublished 1997
5 schema:datePublishedReg 1997-01-01
6 schema:description Four fundamental graph problems, Minimum vertex cover, Maximum independent set, Minimum dominating set and Maximum cut, are shown to be APX-complete even for cubic graphs. This means that unless P=NP these problems do not admit any polynomial time approximation scheme on input graphs of degree bounded by three.
7 schema:editor N6e6f8c3e97a346eca90989f2f5d5e975
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree false
11 schema:isPartOf N47a3a60a83f14b77a81278cc49eee4a6
12 schema:name Hardness of approximating problems on cubic graphs
13 schema:pagination 288-298
14 schema:productId N6568720a6b8f4f959f79c12f3e4fdd14
15 N9a46707a74bf4732b824e3f3270149cd
16 Nff002c22423d4d61b01d8477fc18cd6f
17 schema:publisher N527c3199669b4c90b815d5f55217b3ed
18 schema:sameAs https://app.dimensions.ai/details/publication/pub.1042261594
19 https://doi.org/10.1007/3-540-62592-5_80
20 schema:sdDatePublished 2019-04-15T11:23
21 schema:sdLicense https://scigraph.springernature.com/explorer/license/
22 schema:sdPublisher N1eae5f50e13340d5b72c097cc7110b56
23 schema:url http://link.springer.com/10.1007/3-540-62592-5_80
24 sgo:license sg:explorer/license/
25 sgo:sdDataset chapters
26 rdf:type schema:Chapter
27 N1aadf45c775a458ba9455cab63d5d9e6 rdf:first sg:person.014343100201.33
28 rdf:rest rdf:nil
29 N1eae5f50e13340d5b72c097cc7110b56 schema:name Springer Nature - SN SciGraph project
30 rdf:type schema:Organization
31 N3c493de4f12447e8b72e35d9fa1c4e79 schema:familyName Bovet
32 schema:givenName Daniel Pierre
33 rdf:type schema:Person
34 N44cb91d29c56420daf4f5e330a356691 rdf:first sg:person.015632520461.69
35 rdf:rest N1aadf45c775a458ba9455cab63d5d9e6
36 N47a3a60a83f14b77a81278cc49eee4a6 schema:isbn 978-3-540-62592-6
37 978-3-540-68323-0
38 schema:name Algorithms and Complexity
39 rdf:type schema:Book
40 N527c3199669b4c90b815d5f55217b3ed schema:location Berlin, Heidelberg
41 schema:name Springer Berlin Heidelberg
42 rdf:type schema:Organisation
43 N64146d94ee2147d093186ef95487899e rdf:first N3c493de4f12447e8b72e35d9fa1c4e79
44 rdf:rest N7e48dcd8b36945e2a24fa6e24c49fa68
45 N6568720a6b8f4f959f79c12f3e4fdd14 schema:name doi
46 schema:value 10.1007/3-540-62592-5_80
47 rdf:type schema:PropertyValue
48 N6e6f8c3e97a346eca90989f2f5d5e975 rdf:first Nc066f75f7dfc475aa340fc4f6c11a7a6
49 rdf:rest N64146d94ee2147d093186ef95487899e
50 N7e48dcd8b36945e2a24fa6e24c49fa68 rdf:first Nfbcc794d5f8646ebaf2d9b217d92dde7
51 rdf:rest rdf:nil
52 N9a46707a74bf4732b824e3f3270149cd schema:name dimensions_id
53 schema:value pub.1042261594
54 rdf:type schema:PropertyValue
55 Nc066f75f7dfc475aa340fc4f6c11a7a6 schema:familyName Bongiovanni
56 schema:givenName Giancarlo
57 rdf:type schema:Person
58 Nfbcc794d5f8646ebaf2d9b217d92dde7 schema:familyName Battista
59 schema:givenName Giuseppe
60 rdf:type schema:Person
61 Nff002c22423d4d61b01d8477fc18cd6f schema:name readcube_id
62 schema:value c9503066fae9e82ce016cb4bb15c499186e473d218d19b0ada57d2170315a311
63 rdf:type schema:PropertyValue
64 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
65 schema:name Information and Computing Sciences
66 rdf:type schema:DefinedTerm
67 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
68 schema:name Computation Theory and Mathematics
69 rdf:type schema:DefinedTerm
70 sg:person.014343100201.33 schema:affiliation https://www.grid.ac/institutes/grid.5037.1
71 schema:familyName Kann
72 schema:givenName Viggo
73 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014343100201.33
74 rdf:type schema:Person
75 sg:person.015632520461.69 schema:affiliation https://www.grid.ac/institutes/grid.7841.a
76 schema:familyName Alimonti
77 schema:givenName Paola
78 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015632520461.69
79 rdf:type schema:Person
80 https://www.grid.ac/institutes/grid.5037.1 schema:alternateName Royal Institute of Technology
81 schema:name Numerical Analysis and Computing Science, Royal Institute of Technology, S-100 44 Stockholm, Sweden
82 rdf:type schema:Organization
83 https://www.grid.ac/institutes/grid.7841.a schema:alternateName Sapienza University of Rome
84 schema:name Dip. Informatics Sistemistica, University of Rome “la Sapienza”, Via Salaria 113, 00198 Rome, Italy
85 rdf:type schema:Organization
 




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


...