Improved non-approximability results for vertex cover with density constraints View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

1996

AUTHORS

Andrea E. F. Clementi , Luca Trevisan

ABSTRACT

We provide new non-approximability results for the restrictions of the Min Vertex Cover problem to bounded-degree, sparse and dense graphs. We show that, for a sufficiently large B, the recent 16/15 lower bound proved by Bellare et al. [3] extends with negligible loss to graphs with bounded degree B. Then, we consider sparse graphs with no dense components (i.e. everywhere sparse graphs), and we show a similar result but with a better trade-off between non-approximability and sparsity. Finally we observe that the Min Vertex Cover problem remains APX-complete when restricted to dense graph and thus recent techniques developed by Arora et al. [1] for several Max SNP problems restricted to “dense” instances cannot be applied. More... »

PAGES

333-342

Book

TITLE

Computing and Combinatorics

ISBN

978-3-540-61332-9
978-3-540-68461-9

Author Affiliations

From Grant

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/3-540-61332-3_167

DOI

http://dx.doi.org/10.1007/3-540-61332-3_167

DIMENSIONS

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


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/0903", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Biomedical Engineering", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/09", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Engineering", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Sapienza University of Rome", 
          "id": "https://www.grid.ac/institutes/grid.7841.a", 
          "name": [
            "Dipartimento di Scienze dell'Informazione, Universit\u00e0 di Roma \u201cLa Sapienza\u201d, Via Salaria 113, 00198\u00a0Roma, Italy"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Clementi", 
        "givenName": "Andrea E. F.", 
        "id": "sg:person.011027660123.21", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011027660123.21"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Sapienza University of Rome", 
          "id": "https://www.grid.ac/institutes/grid.7841.a", 
          "name": [
            "Dipartimento di Scienze dell'Informazione, Universit\u00e0 di Roma \u201cLa Sapienza\u201d, Via Salaria 113, 00198\u00a0Roma, Italy"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Trevisan", 
        "givenName": "Luca", 
        "id": "sg:person.015761757701.03", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015761757701.03"
        ], 
        "type": "Person"
      }
    ], 
    "citation": [
      {
        "id": "https://doi.org/10.1016/0022-0000(91)90023-x", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1043200457"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/0304-3975(76)90059-1", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1052030997"
        ], 
        "type": "CreativeWork"
      }
    ], 
    "datePublished": "1996", 
    "datePublishedReg": "1996-01-01", 
    "description": "We provide new non-approximability results for the restrictions of the Min Vertex Cover problem to bounded-degree, sparse and dense graphs. We show that, for a sufficiently large B, the recent 16/15 lower bound proved by Bellare et al. [3] extends with negligible loss to graphs with bounded degree B. Then, we consider sparse graphs with no dense components (i.e. everywhere sparse graphs), and we show a similar result but with a better trade-off between non-approximability and sparsity. Finally we observe that the Min Vertex Cover problem remains APX-complete when restricted to dense graph and thus recent techniques developed by Arora et al. [1] for several Max SNP problems restricted to \u201cdense\u201d instances cannot be applied.", 
    "editor": [
      {
        "familyName": "Cai", 
        "givenName": "Jin-Yi", 
        "type": "Person"
      }, 
      {
        "familyName": "Wong", 
        "givenName": "Chak Kuen", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/3-540-61332-3_167", 
    "inLanguage": [
      "en"
    ], 
    "isAccessibleForFree": true, 
    "isFundedItemOf": [
      {
        "id": "sg:grant.3773495", 
        "type": "MonetaryGrant"
      }
    ], 
    "isPartOf": {
      "isbn": [
        "978-3-540-61332-9", 
        "978-3-540-68461-9"
      ], 
      "name": "Computing and Combinatorics", 
      "type": "Book"
    }, 
    "name": "Improved non-approximability results for vertex cover with density constraints", 
    "pagination": "333-342", 
    "productId": [
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/3-540-61332-3_167"
        ]
      }, 
      {
        "name": "readcube_id", 
        "type": "PropertyValue", 
        "value": [
          "3fd5de76dd6c5d77a23c8c28c0ae6d6571c4a2936d1eaba8991e9ae7da76b22a"
        ]
      }, 
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1013399808"
        ]
      }
    ], 
    "publisher": {
      "location": "Berlin, Heidelberg", 
      "name": "Springer Berlin Heidelberg", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/3-540-61332-3_167", 
      "https://app.dimensions.ai/details/publication/pub.1013399808"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2019-04-15T14: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_8669_00000251.jsonl", 
    "type": "Chapter", 
    "url": "http://link.springer.com/10.1007/3-540-61332-3_167"
  }
]
 

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-61332-3_167'

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-61332-3_167'

Turtle is a human-readable linked data format.

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

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-61332-3_167'


 

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

85 TRIPLES      23 PREDICATES      29 URIs      20 LITERALS      8 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/3-540-61332-3_167 schema:about anzsrc-for:09
2 anzsrc-for:0903
3 schema:author Nb0f3c305042842cbbd2f747a63be7320
4 schema:citation https://doi.org/10.1016/0022-0000(91)90023-x
5 https://doi.org/10.1016/0304-3975(76)90059-1
6 schema:datePublished 1996
7 schema:datePublishedReg 1996-01-01
8 schema:description We provide new non-approximability results for the restrictions of the Min Vertex Cover problem to bounded-degree, sparse and dense graphs. We show that, for a sufficiently large B, the recent 16/15 lower bound proved by Bellare et al. [3] extends with negligible loss to graphs with bounded degree B. Then, we consider sparse graphs with no dense components (i.e. everywhere sparse graphs), and we show a similar result but with a better trade-off between non-approximability and sparsity. Finally we observe that the Min Vertex Cover problem remains APX-complete when restricted to dense graph and thus recent techniques developed by Arora et al. [1] for several Max SNP problems restricted to “dense” instances cannot be applied.
9 schema:editor N065f9685ef9642ed93811fbd60db2572
10 schema:genre chapter
11 schema:inLanguage en
12 schema:isAccessibleForFree true
13 schema:isPartOf N1f6805c4704c4b1c849891de1241a47a
14 schema:name Improved non-approximability results for vertex cover with density constraints
15 schema:pagination 333-342
16 schema:productId N2f3f710ce3db4bfa9e66d7e8ff35228e
17 N2fcf5c6d633d41e083188d533e42f181
18 N5313391aebe64b528de5813e6c0c111c
19 schema:publisher Nb8f5c1b56c2e4bf78e8389b91a708959
20 schema:sameAs https://app.dimensions.ai/details/publication/pub.1013399808
21 https://doi.org/10.1007/3-540-61332-3_167
22 schema:sdDatePublished 2019-04-15T14:23
23 schema:sdLicense https://scigraph.springernature.com/explorer/license/
24 schema:sdPublisher N50b9b310a47649bb9f6e5d6c2ec120d3
25 schema:url http://link.springer.com/10.1007/3-540-61332-3_167
26 sgo:license sg:explorer/license/
27 sgo:sdDataset chapters
28 rdf:type schema:Chapter
29 N065f9685ef9642ed93811fbd60db2572 rdf:first Ncd68a410b5ed4581ac343a40dbc0aeee
30 rdf:rest N220abf53be98447cadf8c4b6506d695b
31 N1f6805c4704c4b1c849891de1241a47a schema:isbn 978-3-540-61332-9
32 978-3-540-68461-9
33 schema:name Computing and Combinatorics
34 rdf:type schema:Book
35 N220abf53be98447cadf8c4b6506d695b rdf:first N3b994dd562e54e5aa865523a1c825cb6
36 rdf:rest rdf:nil
37 N2f3f710ce3db4bfa9e66d7e8ff35228e schema:name doi
38 schema:value 10.1007/3-540-61332-3_167
39 rdf:type schema:PropertyValue
40 N2fcf5c6d633d41e083188d533e42f181 schema:name dimensions_id
41 schema:value pub.1013399808
42 rdf:type schema:PropertyValue
43 N3b994dd562e54e5aa865523a1c825cb6 schema:familyName Wong
44 schema:givenName Chak Kuen
45 rdf:type schema:Person
46 N50b9b310a47649bb9f6e5d6c2ec120d3 schema:name Springer Nature - SN SciGraph project
47 rdf:type schema:Organization
48 N5313391aebe64b528de5813e6c0c111c schema:name readcube_id
49 schema:value 3fd5de76dd6c5d77a23c8c28c0ae6d6571c4a2936d1eaba8991e9ae7da76b22a
50 rdf:type schema:PropertyValue
51 N5b120568e6424b958b2c39de6d674509 rdf:first sg:person.015761757701.03
52 rdf:rest rdf:nil
53 Nb0f3c305042842cbbd2f747a63be7320 rdf:first sg:person.011027660123.21
54 rdf:rest N5b120568e6424b958b2c39de6d674509
55 Nb8f5c1b56c2e4bf78e8389b91a708959 schema:location Berlin, Heidelberg
56 schema:name Springer Berlin Heidelberg
57 rdf:type schema:Organisation
58 Ncd68a410b5ed4581ac343a40dbc0aeee schema:familyName Cai
59 schema:givenName Jin-Yi
60 rdf:type schema:Person
61 anzsrc-for:09 schema:inDefinedTermSet anzsrc-for:
62 schema:name Engineering
63 rdf:type schema:DefinedTerm
64 anzsrc-for:0903 schema:inDefinedTermSet anzsrc-for:
65 schema:name Biomedical Engineering
66 rdf:type schema:DefinedTerm
67 sg:grant.3773495 http://pending.schema.org/fundedItem sg:pub.10.1007/3-540-61332-3_167
68 rdf:type schema:MonetaryGrant
69 sg:person.011027660123.21 schema:affiliation https://www.grid.ac/institutes/grid.7841.a
70 schema:familyName Clementi
71 schema:givenName Andrea E. F.
72 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011027660123.21
73 rdf:type schema:Person
74 sg:person.015761757701.03 schema:affiliation https://www.grid.ac/institutes/grid.7841.a
75 schema:familyName Trevisan
76 schema:givenName Luca
77 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015761757701.03
78 rdf:type schema:Person
79 https://doi.org/10.1016/0022-0000(91)90023-x schema:sameAs https://app.dimensions.ai/details/publication/pub.1043200457
80 rdf:type schema:CreativeWork
81 https://doi.org/10.1016/0304-3975(76)90059-1 schema:sameAs https://app.dimensions.ai/details/publication/pub.1052030997
82 rdf:type schema:CreativeWork
83 https://www.grid.ac/institutes/grid.7841.a schema:alternateName Sapienza University of Rome
84 schema:name Dipartimento di Scienze dell'Informazione, Università di Roma “La Sapienza”, Via Salaria 113, 00198 Roma, Italy
85 rdf:type schema:Organization
 




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


...