On Approximation Properties of the Independent Set Problem for Low Degree Graphs View Full Text


Ontology type: schema:ScholarlyArticle     


Article Info

DATE

1999-04

AUTHORS

P. Berman, T. Fujito

ABSTRACT

. The subject of this paper is the Independent Set problem for bounded node degree graphs. It is shown that the problem remains MAXSNP -complete even when graphs are restricted to being of degree bounded by 3 or to being 3-regular. Some related problems are also shown to be MAXSNP -complete at the lowest possible degree bounds. We next study a better polynomial time approximation of the problem for degree 3 graphs. The performance ratio is improved from the previous best of 5/4 to arbitrarily close to 6/5 for degree 3 graphs and to 7/6 for cubic graphs. When combined with existing techniques this result also leads to approximation ratios, (B+3)/5+ε for the independent set problem and 2-5/(B+3)+ε for the vertex cover problem on graphs of degree B , improving previous bounds for relatively small odd B . More... »

PAGES

115-132

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/s002240000113

DOI

http://dx.doi.org/10.1007/s002240000113

DIMENSIONS

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


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": "Department of Computer Science and Engineering, Pennsylvania State University,   University Park, PA 16802, USA   berman@cse.psu.edu, US", 
          "id": "http://www.grid.ac/institutes/grid.29857.31", 
          "name": [
            "Department of Computer Science and Engineering, Pennsylvania State University,   University Park, PA 16802, USA   berman@cse.psu.edu, US"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Berman", 
        "givenName": "P.", 
        "id": "sg:person.01274506210.27", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01274506210.27"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Department of Electrical Engineering, Hiroshima University,   1-4-1 Kagamiyama, Higashi-Hiroshima 739-8527, Japan   fujito@huis.hiroshima-u.ac.jp, JP", 
          "id": "http://www.grid.ac/institutes/grid.257022.0", 
          "name": [
            "Department of Electrical Engineering, Hiroshima University,   1-4-1 Kagamiyama, Higashi-Hiroshima 739-8527, Japan   fujito@huis.hiroshima-u.ac.jp, JP"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Fujito", 
        "givenName": "T.", 
        "id": "sg:person.015050200671.32", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015050200671.32"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "1999-04", 
    "datePublishedReg": "1999-04-01", 
    "description": "Abstract.  The subject of this paper is the Independent Set problem for bounded node degree graphs. It is shown that the problem remains MAXSNP -complete even when graphs are restricted to being of degree bounded by 3 or to being 3-regular. Some related problems are also shown to be MAXSNP -complete at the lowest possible degree bounds. We next study a better polynomial time approximation of the problem for degree 3 graphs. The performance ratio is improved from the previous best of 5/4 to arbitrarily close to 6/5 for degree 3 graphs and to 7/6 for cubic graphs. When combined with existing techniques this result also leads to approximation ratios, (B+3)/5+\u03b5  for the independent set problem and 2-5/(B+3)+\u03b5  for the vertex cover problem on graphs of degree B , improving previous bounds for relatively small odd B .", 
    "genre": "article", 
    "id": "sg:pub.10.1007/s002240000113", 
    "isAccessibleForFree": false, 
    "isPartOf": [
      {
        "id": "sg:journal.1052098", 
        "issn": [
          "1432-4350", 
          "1433-0490"
        ], 
        "name": "Theory of Computing Systems", 
        "publisher": "Springer Nature", 
        "type": "Periodical"
      }, 
      {
        "issueNumber": "2", 
        "type": "PublicationIssue"
      }, 
      {
        "type": "PublicationVolume", 
        "volumeNumber": "32"
      }
    ], 
    "keywords": [
      "independent set problem", 
      "degree-3 graphs", 
      "set problem", 
      "degree graphs", 
      "low-degree graphs", 
      "polynomial-time approximation", 
      "vertex cover problem", 
      "approximation properties", 
      "time approximation", 
      "degree bounds", 
      "approximation ratio", 
      "previous bounds", 
      "cubic graphs", 
      "cover problem", 
      "graph", 
      "related problems", 
      "bounds", 
      "problem", 
      "performance ratio", 
      "approximation", 
      "degree b", 
      "properties", 
      "technique", 
      "ratio", 
      "results", 
      "degree", 
      "subjects", 
      "paper"
    ], 
    "name": "On Approximation Properties of the Independent Set Problem for Low Degree Graphs", 
    "pagination": "115-132", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1026079541"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/s002240000113"
        ]
      }
    ], 
    "sameAs": [
      "https://doi.org/10.1007/s002240000113", 
      "https://app.dimensions.ai/details/publication/pub.1026079541"
    ], 
    "sdDataset": "articles", 
    "sdDatePublished": "2022-08-04T16:54", 
    "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/article/article_311.jsonl", 
    "type": "ScholarlyArticle", 
    "url": "https://doi.org/10.1007/s002240000113"
  }
]
 

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/s002240000113'

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/s002240000113'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/s002240000113'

RDF/XML is a standard XML format for linked data.

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/s002240000113'


 

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

95 TRIPLES      20 PREDICATES      53 URIs      45 LITERALS      6 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/s002240000113 schema:about anzsrc-for:08
2 anzsrc-for:0802
3 schema:author N5aa2481d08f34fccae49dac4a01f4246
4 schema:datePublished 1999-04
5 schema:datePublishedReg 1999-04-01
6 schema:description Abstract. The subject of this paper is the Independent Set problem for bounded node degree graphs. It is shown that the problem remains MAXSNP -complete even when graphs are restricted to being of degree bounded by 3 or to being 3-regular. Some related problems are also shown to be MAXSNP -complete at the lowest possible degree bounds. We next study a better polynomial time approximation of the problem for degree 3 graphs. The performance ratio is improved from the previous best of 5/4 to arbitrarily close to 6/5 for degree 3 graphs and to 7/6 for cubic graphs. When combined with existing techniques this result also leads to approximation ratios, (B+3)/5+ε for the independent set problem and 2-5/(B+3)+ε for the vertex cover problem on graphs of degree B , improving previous bounds for relatively small odd B .
7 schema:genre article
8 schema:isAccessibleForFree false
9 schema:isPartOf N221e9148efdb4bab8fcf0b7f0303cee7
10 N8471dfe84645486d85aaeb26821495e7
11 sg:journal.1052098
12 schema:keywords approximation
13 approximation properties
14 approximation ratio
15 bounds
16 cover problem
17 cubic graphs
18 degree
19 degree b
20 degree bounds
21 degree graphs
22 degree-3 graphs
23 graph
24 independent set problem
25 low-degree graphs
26 paper
27 performance ratio
28 polynomial-time approximation
29 previous bounds
30 problem
31 properties
32 ratio
33 related problems
34 results
35 set problem
36 subjects
37 technique
38 time approximation
39 vertex cover problem
40 schema:name On Approximation Properties of the Independent Set Problem for Low Degree Graphs
41 schema:pagination 115-132
42 schema:productId Na255f1a5804946eba125e8c3de5c856a
43 Nbda3b9592fb44f3d9647485d9319edeb
44 schema:sameAs https://app.dimensions.ai/details/publication/pub.1026079541
45 https://doi.org/10.1007/s002240000113
46 schema:sdDatePublished 2022-08-04T16:54
47 schema:sdLicense https://scigraph.springernature.com/explorer/license/
48 schema:sdPublisher Nbd17508cca1b48c6ac8a4953edd18e6a
49 schema:url https://doi.org/10.1007/s002240000113
50 sgo:license sg:explorer/license/
51 sgo:sdDataset articles
52 rdf:type schema:ScholarlyArticle
53 N221e9148efdb4bab8fcf0b7f0303cee7 schema:volumeNumber 32
54 rdf:type schema:PublicationVolume
55 N5aa2481d08f34fccae49dac4a01f4246 rdf:first sg:person.01274506210.27
56 rdf:rest N6e115841de434ef2aeecc672bfd414b9
57 N6e115841de434ef2aeecc672bfd414b9 rdf:first sg:person.015050200671.32
58 rdf:rest rdf:nil
59 N8471dfe84645486d85aaeb26821495e7 schema:issueNumber 2
60 rdf:type schema:PublicationIssue
61 Na255f1a5804946eba125e8c3de5c856a schema:name doi
62 schema:value 10.1007/s002240000113
63 rdf:type schema:PropertyValue
64 Nbd17508cca1b48c6ac8a4953edd18e6a schema:name Springer Nature - SN SciGraph project
65 rdf:type schema:Organization
66 Nbda3b9592fb44f3d9647485d9319edeb schema:name dimensions_id
67 schema:value pub.1026079541
68 rdf:type schema:PropertyValue
69 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
70 schema:name Information and Computing Sciences
71 rdf:type schema:DefinedTerm
72 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
73 schema:name Computation Theory and Mathematics
74 rdf:type schema:DefinedTerm
75 sg:journal.1052098 schema:issn 1432-4350
76 1433-0490
77 schema:name Theory of Computing Systems
78 schema:publisher Springer Nature
79 rdf:type schema:Periodical
80 sg:person.01274506210.27 schema:affiliation grid-institutes:grid.29857.31
81 schema:familyName Berman
82 schema:givenName P.
83 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01274506210.27
84 rdf:type schema:Person
85 sg:person.015050200671.32 schema:affiliation grid-institutes:grid.257022.0
86 schema:familyName Fujito
87 schema:givenName T.
88 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015050200671.32
89 rdf:type schema:Person
90 grid-institutes:grid.257022.0 schema:alternateName Department of Electrical Engineering, Hiroshima University, 1-4-1 Kagamiyama, Higashi-Hiroshima 739-8527, Japan fujito@huis.hiroshima-u.ac.jp, JP
91 schema:name Department of Electrical Engineering, Hiroshima University, 1-4-1 Kagamiyama, Higashi-Hiroshima 739-8527, Japan fujito@huis.hiroshima-u.ac.jp, JP
92 rdf:type schema:Organization
93 grid-institutes:grid.29857.31 schema:alternateName Department of Computer Science and Engineering, Pennsylvania State University, University Park, PA 16802, USA berman@cse.psu.edu, US
94 schema:name Department of Computer Science and Engineering, Pennsylvania State University, University Park, PA 16802, USA berman@cse.psu.edu, US
95 rdf:type schema:Organization
 




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


...