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 N5132c0b27c2f4f02ba5c7a4676f87725
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 N3e90909ab6c14c119a2718a12bc09d70
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree false
11 schema:isPartOf Nb5d5fdb4325f4a5d98f47b7ed95f45e4
12 schema:name Hardness of approximating problems on cubic graphs
13 schema:pagination 288-298
14 schema:productId N1499fd52860443288477f7618fdca247
15 N16eabe3f5110473ab19f62ac2fdcb637
16 N8742ff6263fa4f929d0d2669a974ba06
17 schema:publisher N7421d59b5c1a4abcb067a2602d05fcc6
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 N6fdf6dd909ed454a90e4d8ec3d25b9cc
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 N1079d94db44a4a15ad9d2aabcf61e24b rdf:first Nc7b152099dda4b9a9303504d66f573e0
28 rdf:rest Nada00971fcbb43f0b68590d5a13ccff5
29 N1499fd52860443288477f7618fdca247 schema:name dimensions_id
30 schema:value pub.1042261594
31 rdf:type schema:PropertyValue
32 N16eabe3f5110473ab19f62ac2fdcb637 schema:name doi
33 schema:value 10.1007/3-540-62592-5_80
34 rdf:type schema:PropertyValue
35 N1f31c140025040948d08562c4bb54351 schema:familyName Battista
36 schema:givenName Giuseppe
37 rdf:type schema:Person
38 N3e90909ab6c14c119a2718a12bc09d70 rdf:first Nd9ab4a9316eb46fea77628cdfd8a4dea
39 rdf:rest N1079d94db44a4a15ad9d2aabcf61e24b
40 N5132c0b27c2f4f02ba5c7a4676f87725 rdf:first sg:person.015632520461.69
41 rdf:rest Nad50477e6ddd421b95e383e0ca720314
42 N6fdf6dd909ed454a90e4d8ec3d25b9cc schema:name Springer Nature - SN SciGraph project
43 rdf:type schema:Organization
44 N7421d59b5c1a4abcb067a2602d05fcc6 schema:location Berlin, Heidelberg
45 schema:name Springer Berlin Heidelberg
46 rdf:type schema:Organisation
47 N8742ff6263fa4f929d0d2669a974ba06 schema:name readcube_id
48 schema:value c9503066fae9e82ce016cb4bb15c499186e473d218d19b0ada57d2170315a311
49 rdf:type schema:PropertyValue
50 Nad50477e6ddd421b95e383e0ca720314 rdf:first sg:person.014343100201.33
51 rdf:rest rdf:nil
52 Nada00971fcbb43f0b68590d5a13ccff5 rdf:first N1f31c140025040948d08562c4bb54351
53 rdf:rest rdf:nil
54 Nb5d5fdb4325f4a5d98f47b7ed95f45e4 schema:isbn 978-3-540-62592-6
55 978-3-540-68323-0
56 schema:name Algorithms and Complexity
57 rdf:type schema:Book
58 Nc7b152099dda4b9a9303504d66f573e0 schema:familyName Bovet
59 schema:givenName Daniel Pierre
60 rdf:type schema:Person
61 Nd9ab4a9316eb46fea77628cdfd8a4dea schema:familyName Bongiovanni
62 schema:givenName Giancarlo
63 rdf:type schema:Person
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)


...