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/bf01840398", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1036753200", 
          "https://doi.org/10.1007/bf01840398"
        ], 
        "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/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"
      }
    ], 
    "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-12-01T06:20", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20221201/entities/gbq_results/article/article_243.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 N86e204113f5d4a31b36aad5bf3eae996
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 N09ef9872e68647cc867690f369375cbd
14 Ne24d05d0269844baa939ef3297182e2b
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 N7cb99674454949799220dd8848335ae8
42 Nfa14210f30e448afbb6f0a72d5c6a99a
43 schema:sameAs https://app.dimensions.ai/details/publication/pub.1051052098
44 https://doi.org/10.1007/bf01994876
45 schema:sdDatePublished 2022-12-01T06:20
46 schema:sdLicense https://scigraph.springernature.com/explorer/license/
47 schema:sdPublisher N0be88a2be1b44cf394d817b65f646c7b
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 N09ef9872e68647cc867690f369375cbd schema:issueNumber 2
53 rdf:type schema:PublicationIssue
54 N0be88a2be1b44cf394d817b65f646c7b schema:name Springer Nature - SN SciGraph project
55 rdf:type schema:Organization
56 N7cb99674454949799220dd8848335ae8 schema:name dimensions_id
57 schema:value pub.1051052098
58 rdf:type schema:PropertyValue
59 N8694b309955343a9aa00677f59a78dfc rdf:first sg:person.07745452155.78
60 rdf:rest rdf:nil
61 N86e204113f5d4a31b36aad5bf3eae996 rdf:first sg:person.015670714747.94
62 rdf:rest N8694b309955343a9aa00677f59a78dfc
63 Ne24d05d0269844baa939ef3297182e2b schema:volumeNumber 32
64 rdf:type schema:PublicationVolume
65 Nfa14210f30e448afbb6f0a72d5c6a99a schema:name doi
66 schema:value 10.1007/bf01994876
67 rdf:type schema:PropertyValue
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)


...