Approximating maximum independent sets by excluding subgraphs View Full Text


Ontology type: schema:ScholarlyArticle     


Article Info

DATE

1992-06

AUTHORS

Ravi Boppana, Magnús M. Halldórsson

ABSTRACT

An approximation algorithm for the maximum independent set problem is given, improving the best performance guarantee known toO(n/(logn)2). We also obtain the same performance guarantee for graph coloring. The results can be combined into a surprisingly strongsimultaneous performance guarantee for the clique and coloring problems.The framework ofsubgraph-excluding algorithms is presented. We survey the known approximation algorithms for the independent set (clique), coloring, and vertex cover problems and show how almost all fit into that framework. We show that among subgraph-excluding algorithms, the ones presented achieve the optimal asymptotic performance guarantees. More... »

PAGES

180-196

Identifiers

URI

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

DOI

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

DIMENSIONS

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


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/01", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Mathematical Sciences", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0102", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Applied Mathematics", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0103", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Numerical and Computational Mathematics", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "School of Information Science, Japan Advanced Institute of Science and Technology, Hokuriku, Tatsunokuchi, Nomi, 923-12, Ishikawa, Japan", 
          "id": "http://www.grid.ac/institutes/grid.444515.5", 
          "name": [
            "Department of Computer Science, New York University, 10012, New York, NY, USA", 
            "School of Information Science, Japan Advanced Institute of Science and Technology, Hokuriku, Tatsunokuchi, Nomi, 923-12, Ishikawa, Japan"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Boppana", 
        "givenName": "Ravi", 
        "id": "sg:person.015670714747.94", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015670714747.94"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "School of Information Science, Japan Advanced Institute of Science and Technology, Hokuriku, Tatsunokuchi, Nomi, 923-12, Ishikawa, Japan", 
          "id": "http://www.grid.ac/institutes/grid.444515.5", 
          "name": [
            "Department of Computer Science, New York University, 10012, New York, NY, USA", 
            "School of Information Science, Japan Advanced Institute of Science and Technology, Hokuriku, Tatsunokuchi, Nomi, 923-12, Ishikawa, Japan"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Halld\u00f3rsson", 
        "givenName": "Magn\u00fas M.", 
        "id": "sg:person.07745452155.78", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07745452155.78"
        ], 
        "type": "Person"
      }
    ], 
    "citation": [
      {
        "id": "sg:pub.10.1007/3-540-52846-6_74", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1039722520", 
          "https://doi.org/10.1007/3-540-52846-6_74"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bf00290149", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1016394246", 
          "https://doi.org/10.1007/bf00290149"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bf01840398", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1036753200", 
          "https://doi.org/10.1007/bf01840398"
        ], 
        "type": "CreativeWork"
      }
    ], 
    "datePublished": "1992-06", 
    "datePublishedReg": "1992-06-01", 
    "description": "An approximation algorithm for the maximum independent set problem is given, improving the best performance guarantee known toO(n/(logn)2). We also obtain the same performance guarantee for graph coloring. The results can be combined into a surprisingly strongsimultaneous performance guarantee for the clique and coloring problems.The framework ofsubgraph-excluding algorithms is presented. We survey the known approximation algorithms for the independent set (clique), coloring, and vertex cover problems and show how almost all fit into that framework. We show that among subgraph-excluding algorithms, the ones presented achieve the optimal asymptotic performance guarantees.", 
    "genre": "article", 
    "id": "sg:pub.10.1007/bf01994876", 
    "isAccessibleForFree": false, 
    "isPartOf": [
      {
        "id": "sg:journal.1136252", 
        "issn": [
          "0006-3835", 
          "1572-9125"
        ], 
        "name": "BIT Numerical Mathematics", 
        "publisher": "Springer Nature", 
        "type": "Periodical"
      }, 
      {
        "issueNumber": "2", 
        "type": "PublicationIssue"
      }, 
      {
        "type": "PublicationVolume", 
        "volumeNumber": "32"
      }
    ], 
    "keywords": [
      "performance guarantees", 
      "approximation algorithm", 
      "maximum independent set problem", 
      "asymptotic performance guarantees", 
      "maximum independent set", 
      "independent set problem", 
      "vertex cover problem", 
      "better performance guarantee", 
      "independent set", 
      "graph coloring", 
      "same performance guarantee", 
      "set problem", 
      "cover problem", 
      "algorithm", 
      "guarantees", 
      "coloring", 
      "problem", 
      "cliques", 
      "subgraphs", 
      "set", 
      "framework", 
      "one", 
      "results"
    ], 
    "name": "Approximating maximum independent sets by excluding subgraphs", 
    "pagination": "180-196", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1051052098"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/bf01994876"
        ]
      }
    ], 
    "sameAs": [
      "https://doi.org/10.1007/bf01994876", 
      "https://app.dimensions.ai/details/publication/pub.1051052098"
    ], 
    "sdDataset": "articles", 
    "sdDatePublished": "2022-11-24T20:47", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20221124/entities/gbq_results/article/article_252.jsonl", 
    "type": "ScholarlyArticle", 
    "url": "https://doi.org/10.1007/bf01994876"
  }
]
 

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

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

Turtle is a human-readable linked data format.

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

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

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


 

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

104 TRIPLES      21 PREDICATES      52 URIs      40 LITERALS      6 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/bf01994876 schema:about anzsrc-for:01
2 anzsrc-for:0102
3 anzsrc-for:0103
4 schema:author N503d6d03731d4a0c8c4cf93c5fcb1377
5 schema:citation sg:pub.10.1007/3-540-52846-6_74
6 sg:pub.10.1007/bf00290149
7 sg:pub.10.1007/bf01840398
8 schema:datePublished 1992-06
9 schema:datePublishedReg 1992-06-01
10 schema:description An approximation algorithm for the maximum independent set problem is given, improving the best performance guarantee known toO(n/(logn)2). We also obtain the same performance guarantee for graph coloring. The results can be combined into a surprisingly strongsimultaneous performance guarantee for the clique and coloring problems.The framework ofsubgraph-excluding algorithms is presented. We survey the known approximation algorithms for the independent set (clique), coloring, and vertex cover problems and show how almost all fit into that framework. We show that among subgraph-excluding algorithms, the ones presented achieve the optimal asymptotic performance guarantees.
11 schema:genre article
12 schema:isAccessibleForFree false
13 schema:isPartOf N6a9d1332c5da42b7846e3b1647e5373b
14 Nb0533a3ab58e4c3d8b99595850f4401a
15 sg:journal.1136252
16 schema:keywords algorithm
17 approximation algorithm
18 asymptotic performance guarantees
19 better performance guarantee
20 cliques
21 coloring
22 cover problem
23 framework
24 graph coloring
25 guarantees
26 independent set
27 independent set problem
28 maximum independent set
29 maximum independent set problem
30 one
31 performance guarantees
32 problem
33 results
34 same performance guarantee
35 set
36 set problem
37 subgraphs
38 vertex cover problem
39 schema:name Approximating maximum independent sets by excluding subgraphs
40 schema:pagination 180-196
41 schema:productId N16db15b6db6f49f2afcf1be03646e02a
42 N38a5f4f32e7743d09d94a871e6a1426d
43 schema:sameAs https://app.dimensions.ai/details/publication/pub.1051052098
44 https://doi.org/10.1007/bf01994876
45 schema:sdDatePublished 2022-11-24T20:47
46 schema:sdLicense https://scigraph.springernature.com/explorer/license/
47 schema:sdPublisher N144a9684205849849310d3f819694bda
48 schema:url https://doi.org/10.1007/bf01994876
49 sgo:license sg:explorer/license/
50 sgo:sdDataset articles
51 rdf:type schema:ScholarlyArticle
52 N144a9684205849849310d3f819694bda schema:name Springer Nature - SN SciGraph project
53 rdf:type schema:Organization
54 N16db15b6db6f49f2afcf1be03646e02a schema:name doi
55 schema:value 10.1007/bf01994876
56 rdf:type schema:PropertyValue
57 N38a5f4f32e7743d09d94a871e6a1426d schema:name dimensions_id
58 schema:value pub.1051052098
59 rdf:type schema:PropertyValue
60 N503d6d03731d4a0c8c4cf93c5fcb1377 rdf:first sg:person.015670714747.94
61 rdf:rest Na213f8b7db324c97ad6cc3603dd5e2ce
62 N6a9d1332c5da42b7846e3b1647e5373b schema:volumeNumber 32
63 rdf:type schema:PublicationVolume
64 Na213f8b7db324c97ad6cc3603dd5e2ce rdf:first sg:person.07745452155.78
65 rdf:rest rdf:nil
66 Nb0533a3ab58e4c3d8b99595850f4401a schema:issueNumber 2
67 rdf:type schema:PublicationIssue
68 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
69 schema:name Mathematical Sciences
70 rdf:type schema:DefinedTerm
71 anzsrc-for:0102 schema:inDefinedTermSet anzsrc-for:
72 schema:name Applied Mathematics
73 rdf:type schema:DefinedTerm
74 anzsrc-for:0103 schema:inDefinedTermSet anzsrc-for:
75 schema:name Numerical and Computational Mathematics
76 rdf:type schema:DefinedTerm
77 sg:journal.1136252 schema:issn 0006-3835
78 1572-9125
79 schema:name BIT Numerical Mathematics
80 schema:publisher Springer Nature
81 rdf:type schema:Periodical
82 sg:person.015670714747.94 schema:affiliation grid-institutes:grid.444515.5
83 schema:familyName Boppana
84 schema:givenName Ravi
85 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015670714747.94
86 rdf:type schema:Person
87 sg:person.07745452155.78 schema:affiliation grid-institutes:grid.444515.5
88 schema:familyName Halldórsson
89 schema:givenName Magnús M.
90 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07745452155.78
91 rdf:type schema:Person
92 sg:pub.10.1007/3-540-52846-6_74 schema:sameAs https://app.dimensions.ai/details/publication/pub.1039722520
93 https://doi.org/10.1007/3-540-52846-6_74
94 rdf:type schema:CreativeWork
95 sg:pub.10.1007/bf00290149 schema:sameAs https://app.dimensions.ai/details/publication/pub.1016394246
96 https://doi.org/10.1007/bf00290149
97 rdf:type schema:CreativeWork
98 sg:pub.10.1007/bf01840398 schema:sameAs https://app.dimensions.ai/details/publication/pub.1036753200
99 https://doi.org/10.1007/bf01840398
100 rdf:type schema:CreativeWork
101 grid-institutes:grid.444515.5 schema:alternateName School of Information Science, Japan Advanced Institute of Science and Technology, Hokuriku, Tatsunokuchi, Nomi, 923-12, Ishikawa, Japan
102 schema:name Department of Computer Science, New York University, 10012, New York, NY, USA
103 School of Information Science, Japan Advanced Institute of Science and Technology, Hokuriku, Tatsunokuchi, Nomi, 923-12, Ishikawa, Japan
104 rdf:type schema:Organization
 




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


...