A d/2 Approximation for Maximum Weight Independent Set in d-Claw Free Graphs View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2000

AUTHORS

Piotr Berman

ABSTRACT

In this paper we consider the following problem. Given is a d-claw free graph G = (V,E,w) where w: V → R+. Our algorithm finds an independent set A such that w(A*)/w(A)≤ d/2 where A* is an independent that maximizes w(A*). The previous best polynomial time approximation algorithm obtained w(A*)/w(A)≤ 2d/3. More... »

PAGES

214-219

Book

TITLE

Algorithm Theory - SWAT 2000

ISBN

978-3-540-67690-4
978-3-540-44985-0

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/3-540-44985-x_19

DOI

http://dx.doi.org/10.1007/3-540-44985-x_19

DIMENSIONS

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


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/08", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Information and Computing Sciences", 
        "type": "DefinedTerm"
      }, 
      {
        "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"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Dept. of Computer Science and Engineering, The Pennsylvania State University, USA", 
          "id": "http://www.grid.ac/institutes/grid.29857.31", 
          "name": [
            "Dept. of Computer Science and Engineering, The Pennsylvania State University, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Berman", 
        "givenName": "Piotr", 
        "id": "sg:person.01274506210.27", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01274506210.27"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "2000", 
    "datePublishedReg": "2000-01-01", 
    "description": "In this paper we consider the following problem. Given is a d-claw free graph G = (V,E,w) where w: V \u2192 R+. Our algorithm finds an independent set A such that w(A*)/w(A)\u2264 d/2 where A* is an independent that maximizes w(A*). The previous best polynomial time approximation algorithm obtained w(A*)/w(A)\u2264 2d/3.", 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/3-540-44985-x_19", 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-540-67690-4", 
        "978-3-540-44985-0"
      ], 
      "name": "Algorithm Theory - SWAT 2000", 
      "type": "Book"
    }, 
    "keywords": [
      "best polynomial-time approximation algorithm", 
      "polynomial-time approximation algorithm", 
      "maximum weight independent set", 
      "time approximation algorithm", 
      "independent set", 
      "approximation algorithm", 
      "algorithm", 
      "free graphs", 
      "set", 
      "graph", 
      "graph G", 
      "free graph G", 
      "approximation", 
      "independent", 
      "problem", 
      "paper"
    ], 
    "name": "A d/2 Approximation for Maximum Weight Independent Set in d-Claw Free Graphs", 
    "pagination": "214-219", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1051241645"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/3-540-44985-x_19"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/3-540-44985-x_19", 
      "https://app.dimensions.ai/details/publication/pub.1051241645"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-09-02T16:16", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20220902/entities/gbq_results/chapter/chapter_440.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/3-540-44985-x_19"
  }
]
 

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-44985-x_19'

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-44985-x_19'

Turtle is a human-readable linked data format.

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

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-44985-x_19'


 

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

69 TRIPLES      21 PREDICATES      40 URIs      33 LITERALS      6 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/3-540-44985-x_19 schema:about anzsrc-for:08
2 anzsrc-for:0802
3 schema:author N9712e813d787499bb98875e238f354d0
4 schema:datePublished 2000
5 schema:datePublishedReg 2000-01-01
6 schema:description In this paper we consider the following problem. Given is a d-claw free graph G = (V,E,w) where w: V → R+. Our algorithm finds an independent set A such that w(A*)/w(A)≤ d/2 where A* is an independent that maximizes w(A*). The previous best polynomial time approximation algorithm obtained w(A*)/w(A)≤ 2d/3.
7 schema:genre chapter
8 schema:isAccessibleForFree false
9 schema:isPartOf N96bc7a607d524f87a8c051ab25572c2e
10 schema:keywords algorithm
11 approximation
12 approximation algorithm
13 best polynomial-time approximation algorithm
14 free graph G
15 free graphs
16 graph
17 graph G
18 independent
19 independent set
20 maximum weight independent set
21 paper
22 polynomial-time approximation algorithm
23 problem
24 set
25 time approximation algorithm
26 schema:name A d/2 Approximation for Maximum Weight Independent Set in d-Claw Free Graphs
27 schema:pagination 214-219
28 schema:productId N02fa79b6dabd4861b681933191c61d73
29 N243c6d4cc17d4f758a4718d2ffa9ce76
30 schema:publisher Nd70ebf0581c44c67989bca38f1068456
31 schema:sameAs https://app.dimensions.ai/details/publication/pub.1051241645
32 https://doi.org/10.1007/3-540-44985-x_19
33 schema:sdDatePublished 2022-09-02T16:16
34 schema:sdLicense https://scigraph.springernature.com/explorer/license/
35 schema:sdPublisher Nce1b7219028442a59d61835220b90a6b
36 schema:url https://doi.org/10.1007/3-540-44985-x_19
37 sgo:license sg:explorer/license/
38 sgo:sdDataset chapters
39 rdf:type schema:Chapter
40 N02fa79b6dabd4861b681933191c61d73 schema:name doi
41 schema:value 10.1007/3-540-44985-x_19
42 rdf:type schema:PropertyValue
43 N243c6d4cc17d4f758a4718d2ffa9ce76 schema:name dimensions_id
44 schema:value pub.1051241645
45 rdf:type schema:PropertyValue
46 N96bc7a607d524f87a8c051ab25572c2e schema:isbn 978-3-540-44985-0
47 978-3-540-67690-4
48 schema:name Algorithm Theory - SWAT 2000
49 rdf:type schema:Book
50 N9712e813d787499bb98875e238f354d0 rdf:first sg:person.01274506210.27
51 rdf:rest rdf:nil
52 Nce1b7219028442a59d61835220b90a6b schema:name Springer Nature - SN SciGraph project
53 rdf:type schema:Organization
54 Nd70ebf0581c44c67989bca38f1068456 schema:name Springer Nature
55 rdf:type schema:Organisation
56 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
57 schema:name Information and Computing Sciences
58 rdf:type schema:DefinedTerm
59 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
60 schema:name Computation Theory and Mathematics
61 rdf:type schema:DefinedTerm
62 sg:person.01274506210.27 schema:affiliation grid-institutes:grid.29857.31
63 schema:familyName Berman
64 schema:givenName Piotr
65 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01274506210.27
66 rdf:type schema:Person
67 grid-institutes:grid.29857.31 schema:alternateName Dept. of Computer Science and Engineering, The Pennsylvania State University, USA
68 schema:name Dept. of Computer Science and Engineering, The Pennsylvania State University, USA
69 rdf:type schema:Organization
 




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


...