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-08-04T17:22", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20220804/entities/gbq_results/chapter/chapter_92.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 N4775ff03e96f4fb68f78c829dad7ebb8
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 N5b5c8771d538495aaefe653568472d61
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 Na79655e77c1b4c6b9c73f276f4a964f8
29 Nb2a46a250b974d3dbd6c8685da05ac24
30 schema:publisher N46e6647aa95346b28adc22493a2bc6f6
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-08-04T17:22
34 schema:sdLicense https://scigraph.springernature.com/explorer/license/
35 schema:sdPublisher N9d422c7acfef4ab49e803098707205fb
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 N46e6647aa95346b28adc22493a2bc6f6 schema:name Springer Nature
41 rdf:type schema:Organisation
42 N4775ff03e96f4fb68f78c829dad7ebb8 rdf:first sg:person.01274506210.27
43 rdf:rest rdf:nil
44 N5b5c8771d538495aaefe653568472d61 schema:isbn 978-3-540-44985-0
45 978-3-540-67690-4
46 schema:name Algorithm Theory - SWAT 2000
47 rdf:type schema:Book
48 N9d422c7acfef4ab49e803098707205fb schema:name Springer Nature - SN SciGraph project
49 rdf:type schema:Organization
50 Na79655e77c1b4c6b9c73f276f4a964f8 schema:name doi
51 schema:value 10.1007/3-540-44985-x_19
52 rdf:type schema:PropertyValue
53 Nb2a46a250b974d3dbd6c8685da05ac24 schema:name dimensions_id
54 schema:value pub.1051241645
55 rdf:type schema:PropertyValue
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)


...